背包理论基础
01 背包（二维）
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
背包最大重量为4。
物品为：
| 重量 | 价值 | |
|---|---|---|
| 物品0 | 1 | 15 |
| 物品1 | 3 | 20 |
| 物品2 | 4 | 30 |
问背包能背的物品最大价值是多少？
思路：依然是动态规划。
解决：动态规划五步曲
1.确定dp数组及下标含义；
dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
2.确定递推公式；
考虑dp[i][j]是如何推导过来；
①加入第i件物品；
加入第i件物品后，相较于第i-1个物品，加入第i件物品后价值总和就等于dp[i-1][j-weight[i]]+value[i]。
②第i件物品加入重量超标，不加入；
不加入价值总和就是放入第i-1个物品后价值总和：dp[i-1][j]。
所以dp[i][j]=max(dp[i-1][j]，dp[i-1][j-weight[i]]+value[i])；
3.确定dp数组初始化；
首先当j=0时，也就是书包最大重量为0时，dp[i][0]=0;其次只放物品0时，背包价值总和都是15，所以dp[0][j]=15(j>weight[0])。注意这里容量要大于第一个物品的重量。
4.确定遍历顺序；
遍历顺序肯定是从左向右，从上到下，最后遍历到右下角。
5.举例推导dp数组。
代码：
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(),vector<int>(bagweight+1,0));//i是物品数量，j是背包容量
//初始化
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;
int main() {
test_2_wei_bag_problem1();
}
01 背包（一维）
例子：背包最大重量为4。
物品为：
| 重量 | 价值 | |
|---|---|---|
| 物品0 | 1 | 15 |
| 物品1 | 3 | 20 |
| 物品2 | 4 | 30 |
问背包能背的物品最大价值是多少？
思路：对于背包问题其实状态都是可以压缩的。
在使用二维数组的时候，递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);
与其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）。
解决：动态规划五步曲
1.确定dp[j]的含义；
dp[j]表示容量为j的背包，能背的最大价值。
2.确定递推公式；
dp[j]=max(dp[j]，dp[j-weight[i]]+value[i])；这里还是一样可以选择放i物品或者不放。
3.确定dp初始化；
最开始j=0时候，装不了物品。dp[0]=0;
4.确定遍历顺序；
举一个例子：物品0的重量weight[0] = 1，价值value[0] = 15
如果正序遍历
dp[1] = dp[1 - weight[0]] + value[0] = 15
dp[2] = dp[2 - weight[0]] + value[0] = 30
此时dp[2]就已经是30了，意味着物品0，被放入了两次，所以不能正序遍历。
倒序就是先算dp[2]
dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0）
dp[1] = dp[1 - weight[0]] + value[0] = 15
所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。
5.举例推导公式。
代码：
void test_1_wei_bag_problem() {
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;
}
int main() {
test_1_wei_bag_problem();
}416. 分割等和子集 - 力扣（LeetCode）
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。
思路：这个问题如何转化成背包问题？最好的结果就是分成两个子集和相等，既然和相等，那么子集的和就是总和的一半，也就是说，从nums数组种取出元素，能够满足和等于总和的一半，那么结果就是true。那这里背包容量就是总和的一半，物品的价值就是元素数值，物品重量可以说每个都是1，也可以不用管。
解决：动态规划五步曲：
1.确定dp[i]的含义；
j表示背包总容量，这里相当于目标值，从目标值递减遍历；背的最大重量为dp[j]，当dp[j]等于目标值时说明可以分割成两个子集。
2.确定递推公式；
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])。
3.确定dp初始化；
初始化和一维数组一样，都设置为0。
4.确定遍历顺序；
遍历顺序从大到小，防止重复放入。
5.举例推导公式。
代码：
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum=0;
for(int i=0;i<nums.size();i++){
sum+=nums[i];
}
vector<int> dp(10001, 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]);
}
}
if (dp[target] == target) return true;
return false;
}
};
