# 01 背包理论基础
01 背包模板题：有 n 件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是 weight [i]，得到的价值是 value [i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
背包最大重量为 4，物品为：
| 重量 | 价值 | |
|---|---|---|
| 物品 0 | 1 | 15 |
| 物品 1 | 3 | 20 |
| 物品 2 | 4 | 30 |
# 二维 dp 数组
- 确定 dp 数组以及下标含义
dp [i][j]: 从下标为 [0-i] 的物品里任意取，放进容量为 j 的背包，价值总和最大是多少。
- 确定递推公式
两个方向可推导出 dp [i][j]：
- 不放物品 i: 由 dp [i - 1][j] 推出
- 放物品 i：由 dp [i - 1][j - weight [i]] + value [i] 推出
- dp 数组初始化
从 dp [i][j] 定义出发，如果背包容量 j 为 0，无论放什么 dp 一定为 0。因此 dp [i][0] = 0。
从状态转移方程看，dp [i][j] 由 i-1 推导出来，那么 dp [0][j] 要初始化为。很明显当 j < weight [0] 时，dp [0][j] = 0；当 j >= weight [0] 时，dp [0][j] = value [0]。
- 确定遍历顺序
先遍历背包或者物品都可以。
- 先遍历物品
- 先遍历背包
- 举例推导 dp 数组
void bag_01() { | |
vector<int> weight = {1, 3, 4}; | |
vector<int> value = {15, 20, 30}; | |
int bagweight = 4; | |
// 二维数组 | |
vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0)); | |
// 初始化 | |
for (int j = weight[0]; j <= bagweight; j++) { | |
dp[0][j] = value[0]; | |
} | |
//weight 数组的大小 就是物品个数 | |
for(int i = 1; i < weight.size(); i++) { // 遍历物品 | |
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量 | |
if (j < weight[i]) dp[i][j] = dp[i - 1][j]; | |
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); | |
} | |
} | |
cout << dp[weight.size() - 1][bagweight] << endl; | |
} |
# 一维 dp 数组（滚动数组）
在使用二维数组的时候，递推公式：
其实可以发现如果把 dp [i - 1] 那一层拷贝到 dp [i] 上，表达式完全可以是：
这样可以只用一个一维数组 dp [j]。
- 确定 dp 数组以及下标含义
dp [j]: 表示容量为 j 的背包，所背物品的价值最大为 dp [j]
- 递推公式
dp [j] 可以通过 dp [j - weight [i]] 推导出来，dp [j - weight [i]] 表示容量为 j - weight [i] 的背包所背的最大价值。
此时 dp [j] 有两个选择，一个是取自己 dp [j] 相当于 二维 dp 数组中的 dp [i-1][j]，即不放物品 i，一个是取 dp [j - weight [i]] + value [i]，即放物品 i，指定是取最大的，毕竟是求最大价值，
- dp 数组如何初始化
dp [0] = 0，因为背包容量为 0，所背物品最大价值就是 0.
dp 数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非 0 下标都初始化为 0 就可以了。
这样才能让 dp 数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了。
- dp 数组遍历顺序
二维 dp 遍历的时候，背包容量是从小到大，而一维 dp 遍历的时候，背包是从大到小。
倒序遍历是为了保证物品 i 只被放入一次！。如果一旦正序遍历了，那么物品 0 就会被重复加入多次！
此外一定要先遍历物品再遍历背包。因为一维 dp 的写法，背包容量一定是要倒序遍历（原因上面已经讲了），如果遍历背包容量放在上一层，那么每个 dp [j] 就只会放入一个物品，即：背包里只放入了一个物品。
- 举例推导 dp 数组
void bag_01() { | |
vector<int> weight = {1, 3, 4}; | |
vector<int> value = {15, 20, 30}; | |
int bagWeight = 4; | |
// 初始化 | |
vector<int> dp(bagWeight + 1, 0); | |
for(int i = 0; i < weight.size(); i++) { // 遍历物品 | |
for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量 | |
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); | |
} | |
} | |
cout << dp[bagWeight] << endl; | |
} |
# 分割等和子集
题目链接🔗
只要找到集合里能够出现 sum / 2 的子集总和，就算是可以分割成两个相同元素和子集了。
将其抽象成背包问题有以下四点：
- 背包的体积为 sum / 2
- 背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
- 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
- 背包中每一个元素是不可重复放入。
- 确定 dp 数组以及下标含义
dp [j]: 表示 背包总容量（背包内元素和）是 sum/2，放进元素后，背包的最大重量为 dp [j]。
当 dp [sum/2] == sum/2 的时候，就装满了。
- 确定递推公式
本题，相当于背包里放入数值，那么物品 i 的重量是 nums [i]，其价值也是 nums [i]。
所以递推公式：$$dp [j] = max (dp [j], dp [j - nums [i]] + nums [i])$$
- dp 数组如何初始化
本题题目中只包含正整数的非空数组，所以非 0 下标的元素初始化为 0 就可以了。
- 确定遍历顺序
如果使用一维 dp 数组，物品遍历的 for 循环放在外层，遍历背包的 for 循环放在内层，且内层 for 循环倒序遍历。
- 举例推导 dp 数组
dp [j] 的数值一定是小于等于 j 的。
如果 dp [j] == j 说明，集合中的子集总和正好可以凑成总和 j，理解这一点很重要。
用例 1，输入 [1,5,11,5] 为例，如图：
class Solution { | |
public: | |
bool canPartition(vector<int>& nums) { | |
int sum = 0; | |
// 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200 | |
// 总和不会大于 20000，背包最大只需要其中一半，所以 10001 大小就可以了 | |
vector<int> dp(10001, 0); | |
int sum = accumulate(nums.begin(), nums.end(), 0); | |
if (sum % 2 == 1) return false; | |
int target = sum / 2; | |
for(int i = 0; i < nums.size(); i++) { | |
for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历 | |
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); | |
} | |
} | |
// 集合中的元素正好可以凑成总和 target | |
if (dp[target] == target) return true; | |
return false; | |
} | |
}; |
# 最后一块石头的重量
题目链接🔗
本题尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成 01 背包问题了。思路和分割等和子集一致。
本题物品的重量为 stones [i]，物品的价值也为 stones [i]。
那么递推公式为：
分成两堆石头，一堆是 dp [sum/2]，另一堆就是 sum - dp [sum/2]。
因为整型 int 的除法是向下取整，因此 sum - dp [sum/2] >= dp [sum/2]。
两堆相减就是最小石头重量。
class Solution { | |
public: | |
int lastStoneWeightII(vector<int>& stones) { | |
vector<int> dp(15001, 0); | |
int sum = accumlate(stones.begin(), stones.end(), 0); | |
int target = sum / 2; | |
for (int i = 0; i < stones.size(); i++) { // 遍历物品 | |
for (int j = target; j >= stones[i]; j--) { // 遍历背包 | |
dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]); | |
} | |
} | |
return sum - dp[target] - dp[target]; | |
} | |
}; |
