[笔记]动态规划之01背包问题

本文主要是介绍[笔记]动态规划之01背包问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

01背包

每件物品只能放入1次，装入哪些物品能让背包内物品总价值最高？

暴力解法：回溯算法 - 时间复杂度 $O(2^n)$

确定dp数组下标含义

dp[i][j] - 从下标为[0]到[i]的物品里取，放入容量为j的背包，此时的最大价值总和
确定递推公式
- 不放物品i：dp[i][j] = dp[i - 1][j]（物品重量大于背包容量，物品i放不进包里，背包价值不变；
- 放物品i：dp[i][j] = dp[i - 1][j - weight[i]] + value[i]（dp[i - 1][j - weight[i]]是容量为j - weight[i]时未放物品i的最大价值，dp[i - 1][j - weight[i]] + value[i]是此时放入物品i后背包的最大价值；
- 综上：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
初始化dp数组
1. 容量j为0时，背包价值总和一定为0；
2. 当j < weight[0]时，dp[0][j] = 0(背包容量比第0号物品小，放不进背包）；
3. 当j > weight[0]时，dp[0][j] = value[0]（背包可以放下第0号物品）；
```
//参考代码如下，全部初始化为0则可省略第一个for循环
for (int j = 0; j < weight[0]; j++)dp[0][j] = 0;
for (int j = weight[0]; j <= bagweight; j++) dp[0][j] = value[0];
```
确定遍历顺序
1. 先遍历物品，后遍历背包
2. 先遍历背包，后遍历物品
3. 本质上：dp[i][j]由前序数据推出，for循环遍历次序不影响公式推导
举例推导dp数组

所谓滚动数组，就是通过一维数组的方式压缩存储背包问题的状态。

确定dp数组下标含义
- dp[i][j] - 从下标为[0]到[i]的物品里取，放入容量为j的背包，此时的最大价值总和；
- dp[j] - 容量为j的背包，所装物品的最大价值总和；
确定dp数组递推公式
1. 不放物品i：dp[j] = dp[j]；
2. 放物品i：dp[j] = dp[j - weight[i]] + value[i]；
3. 综上，递推式为dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
初始化dp数组
- dp[0] = 0;
- 其它下标可以初始化为0；
确定遍历顺序
- 倒序遍历：保证物品i只被放入一次！
  
  dp[i][j]是由上一层dp[i - 1][ ]计算而来，当前层的dp[i][j]并不会被覆盖，顺序逆序遍历物品i都只被放入一次。如果顺序遍历dp[j]数组，就相当于dp[i][j]由层dp[i][ ]计算而来，这个过程就重复放入物品i了。
- 先遍历物品，再嵌套遍历背包容量
  
  倒序遍历，如果先遍历背包容量，再嵌套物品，那么背包里都只放入了一个物品。
举例推导dp数组