背包三讲
复现代码随想录DP专题
动态规划五部曲
确定dp数组以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
打印数组（与自己的推导比较，看哪里错了）
01背包
有N件物品和⼀个最多能被重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装⼊背包里物品价值总和最大？
1. 例题（二维数组解法）
题目
背包最大重量为4
| 重量 | 价值 |
|
| 物品0 | 1 |
15 |
| 物品1 | 3 |
20 |
| 物品2 | 4 |
30 |
问：背包能背的物品最大价值是多少？
思路
五部曲
数组含义
使用二维数组 dp[i][j]，含义：从下标为 [ 0 ∼ i ] 的物品中任意取，放入容量为 j jj 的背包，价值总和最大为多少
递推公式由两个方向推出
一、不放物品 i的最大价值
背包容量为 j，但不放物品 i 时的最大价值，即 dp[i-1][j]
二、放物品 i的最大价值
先找到 dp[i-1][j-weight[i]]，含义：i − 1 保证了不放物品 i，背包容量为 j − w e i g h t [ i ]其实就是为了给后续放物品 i 一个预留量，保证放了物品 i ii 后背包不会溢出，所以最大价值为 dp[i-1][j-weight[i]]+value[i]
递推公式：
d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − w e i g h t [ i ] ] + v a l u e [ i ] )
数组初始化
背包容量 j 为零时，显然价值为零
只选物品0，即第一行，显然只要物品0重量小于等于背包重量 j，价值就为物品0的价值，否则为零
确定遍历顺序
先遍历背包还是物品都可以
dp[i][j] 所需的数据在其左上方
测试用例
代码展示
#include <iostream> #include <cmath> #include <vector> using namespace std; void test_2_wei_bag_problem1() { vector<int> weight = {1, 3, 4}; vector<int> value = {15, 20, 30}; int bagWeight = 4; vector<vector<int>> dp(weight.size() + 1, vector<int>(bagWeight + 1)); for (int i = 1; i < bagWeight + 1; i++) { if (weight[0] <= i) { dp[0][i] = value[0]; } } for (int j = 1; j < bagWeight + 1; j++) { for (int i = 1; i < weight.size(); i++) { 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]; } int main() { test_2_wei_bag_problem1(); return 0; }
2. 例题（滚动数组解法）
还是之前的例子，可以用滚动数组将数组降为一维
d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − w e i g h t [ i ] ] + v a l u e [ i ] )
由递推公式得： dp[i][j] 只和它的上一行有关，且有关元素的行数为 i − 1，列数 ≤ j 。那么我们就可以将数组压缩成一维
dp[i−1][j−weight[i]] |
dp[i−1][j] |
| 欲求元素 |
看这张表，如果数组是一维的情况，那么在算出欲求元素后，其实是将欲求元素覆盖掉 dp[i-1][j]，并且我们的遍历顺序也要改变。在二维情况下，我们是按从左到右的顺序求的，但在一维中，必须从右向左！因为在求欲求元素时，我们要保证 dp[i-1][j-weight[i]] 未被覆盖！同时，必须按照先遍历物品，再嵌套遍历背包的顺序。
01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次
举例：
假设物品0重量 w e i g h t [ 0 ] = 1 ，价值 v a l u e [ 0 ] = 15
如果是正序遍历
d p [ 1 ] = d p [ 1 − w e i g h t [ 0 ] ] + v a l u e [ 0 ] = 15
d p [ 2 ] = d p [ 2 − w e i g h t [ 0 ] ] + v a l u e [ 0 ] = 30
在第一行运行后 d p [ 1 ] 的状态已经发生改变，意味着已经放了物品0，而第二行运行后，叠加了改变后的 d p [ 1 ] ，意味着物品0被放了两次。
那么为什么之前在写二维数组的时候是正序的？
因为我们实际求的是上一行的状态，也就是不放当前物品的情况，只不过在滚动数组中，压缩了状态。也即当前元素的公式被运行后，当前元素的状态（在当前行，包括物品0）覆盖了先前状态（在上一行，不含物品0），所以一维中倒序是为了保证物品只被放入一次！
#include <iostream> #include <cmath> #include <vector> using namespace std; void test_1_wei_bag_problem1() { vector<int> weight = {1, 3, 4}; vector<int> value = {15, 20, 30}; int bagWeight = 4; vector<int> dp(bagWeight + 1); 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]; } int main() { test_1_wei_bag_problem1(); return 0; }
3. 分割等和子集（LeetCode-416）
题目
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。
提示：
1 <= nums.length <= 200
1 <= nums[i] <= 100
思路
完全背包和01背包区别？
完全背包中一个商品可以放 无数次
01背包中一个商品只能放一次
本题如何套？
分割成两个子集且元素和相等，即背包容量为 s u m / 2 sum/2sum/2
物品重量为 n u m s [ i ] nums[i]nums[i]，价值也为 n u m s [ i ] nums[i]nums[i]
背包正好装满，就说明找到了 s u m / 2 sum/2sum/2
五部曲
dp[i] 含义
背包容量为 i 时，最大可以凑出的子集和
递推公式
本题中，物品重量为 n u m s [ i ] ，价值也为 n u m s [ i ]
d p [ j ] = m a x ( d p [ j ] , d p [ j − n u m s [ i ] ] + n u m s [ i ] )
数组初始化
都初始化为零
遍历顺序
先遍历物品，嵌套遍历背包，且背包遍历要倒序，不懂的回看例题
测试用例
代码展示
class Solution { public: bool canPartition(vector<int> &nums) { int sum = accumulate(nums.begin(), nums.end(), 0); if (sum % 2) { return false; } int target = sum / 2; vector<int> dp(target + 1); 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]); if (dp[target] == target) { return true; } } } return false; } };
对比卡尔哥的解法，用 target+1 做为数组大小，优化了空间。遍历中遇到一个吻合的直接返回 true，优化了时间。
4. 最后一块石头的重量Ⅱ（LeetCode-1049）
题目
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
示例 1：
输入：stones = [2,7,4,1,8,1] 输出：1 解释： 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]， 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]， 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]， 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
示例 2：
输入：stones = [31,26,33,21,40] 输出：5
示例 3：
输入：stones = [1,2] 输出：1
提示：
1 <= stones.length <= 30
1 <= stones[i] <= 100
思路
如何套？
目的是求 最小的可能重量，其实也就是凑重量尽可能相等的两堆。举个例子 10，1，2，2，2，2，2 。我们就可以分为重量为 11 1111 和 10 1010 的两堆。
五部曲
dp[j] 含义
重量为 j jj 的背包最大可以装的石头重量和
递推公式
本题中，物品重量为 s t o n e s [ i ] ，价值也为 s t o n e s [ i ]
d p [ j ] = m a x ( d p [ j ] , d p [ j − s t o n e s [ i ] ] + s t o n e s [ i ] )
数组初始化
设默认值零即可
遍历顺序
先遍历物品，嵌套遍历背包，且背包遍历要倒序
测试用例
代码展示
class Solution { public: int lastStoneWeightII(vector<int> &stones) { int sum = accumulate(stones.begin(), stones.end(), 0); int target = sum / 2; vector<int> dp(target + 1); 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]; } };
开始时没有考虑到问题是最小的可能重量。在 stones = [31,26,33,21,40] 这个样例中：一堆为 31，26，21 重量和为 78 7878，另一堆为 33，40 重量和为 73 7373。按照代码求法，target=75。求的是 dp[75]。为什么不是求 dp[73]？回看数组定义：重量为 j jj 的背包最大可以装的石头重量和。可以看出：其实 dp[75] 与 dp[73] 是相等的
5. 目标和（LeetCode-494）
题目
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1：
输入：nums = [1,1,1,1,1], target = 3 输出：5 解释：一共有 5 种方法让最终目标和为 3 。 -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3
示例 2：
输入：nums = [1], target = 1 输出：1
提示：
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000
思路
怎么套？
分成两堆， l e f t − r i g h t = t a r g e t
又因为 l e f t + r i g h t = s u m
所以 l e f t = ( s u m + t a r g e t )/ 2
这和以前遇到的题目 不一样
先前：容量为 i 的背包，最多能装多少？
这次：填满容量为 i 的背包，有多少种方法？
五部曲
数组定义
dp[j] 表示：填满容量为 j 的背包，有 dp[j] 种方法
递推公式
分两种情况，一种是不包含当前物品的方法数量，另一种是包含当前物品的方法数量。我们要求的就是二者 之和。为了方便，直接使用一维数组展示：
d p [ j ] = d p [ j ] + d p [ j − n u m s [ i ] ]
数组初始化
如果是二维数组，也就是要初始化第一行，即只有物品零的情况，可以想见，填满背包容量为零的方法有一种，就是不装东西。但填满不为零的背包的方法却为零，除非物品重量等于背包容量。所以在一维数组中初始化应该是 dp[0]=1 其他为0
遍历顺序
先遍历物品，嵌套遍历背包，且背包遍历要倒序
测试用例
代码展示
class Solution { public: int findTargetSumWays(vector<int> &nums, int target) { int sum = accumulate(nums.begin(), nums.end(), 0); if ((sum < target) || ((sum + target) % 2) || ((sum + target) < 0)) { return 0; } int left = (sum + target) / 2; vector<int> dp(left + 1); dp[0] = 1; for (int i = 0; i < nums.size(); i++) { for (int j = left; j >= nums[i]; j--) { dp[j] += dp[j - nums[i]]; } } return dp[left]; } };
