题目：416.分割等和子集
思路：只要找到集合里能够出现sum/2的子集总和，就算是可以分割成两个相同元素和子集了。
1.dp[j]含义：背包容量为j时，放进物品后，背的最大重量为dp[j]
那么如果背包容量为target， dp[target]就是装满 背包之后的重量，所以 当 dp[target] == target 的时候，背包就装满了。
2.递推公式：dp[j] = max(dp[j], dp[j - nums[j]] + nums[j])
本题，相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。
3.初始化：如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，如果题目给的价值有负数，那么非0下标就要初始化为负无穷。
4.遍历顺序：先物品后背包；背包从后到前（若从前到后则每个物品会放入多次）
5.举例推到dp数组：dp[target]里存的是最大重量
代码如下：
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
//dp[i]中的i表示背包内的总和
//题目中说：每个数组中的元素不会超过 100，数组大小不会超过 200
//总和不会大于20000，背包最大只需要其中的一半，所以10001大小就可以了
vector<int> dp(10001, 0);
for(int i = 0; i < nums.size(); i++) {
sum += nums[i];
}
//库函数一步求和：int sum = accumulate(nums.begin(), nums.end(), 0);
if(sum % 2 == 1) return false;
int target = sum / 2;
//开始01背包
for(int i = 0; i < nums.size(); i++){
for(int j = target; j >= nums[i]; j--) { //每一个元素一定是不可重复放入，所以大小从大到小遍历
//j代表背包容量，当j>nums[i]时，j - nums[i]才会大于0，背包里才能放下它
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); //每次都做选择，求每次的最优解
}
}
//集合中的元素正好可以凑成总和target
if(dp[target] == target) return true;
return false;
}
};题目：1049.最后一块石头的重量||
思路：将石头尽可能的分为重量总和近似相等的两堆，是两堆相撞，得到相撞所剩下的最小值
1.dp[j]含义:背包容量为j时，最大价值为dp[j]。每个石头的重量即为每个石头的价值（这一点要注意）。
如何定义dp数组大小？极端情况下所有石头一共中3000，因为本题将石头尽可能的分为重量总和近似相等的两堆，所以背包容量1500就够了
2.递推公式：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])；
3.初始化：0
4.遍历顺序
5.打印dp数组
代码如下：
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int sum = 0;
for(int i = 0; i < stones.size(); i++){
sum += stones[i];
}
vector<int> dp(1501, 0);
int target = sum / 2; //target只会向下取整
//开始遍历01背包
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];
}
};题目：494.目标和（可以尝试一下回溯实现，不过会超时）
1.dp[i]含义：装满容量为 j 的背包有 dp[j] 种方法。
2.状态转移方程：dp[j] += dp[j - nums[i]];（求装满背包的方法总数都是用这个）
3.初始化：dp[0] = 1,其余为0（这里是求方法数，而不是“最大价值”）
4.遍历顺序
5.打印dp
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = 0;
for(int i = 0; i < nums.size(); i++){
sum += nums[i];
}
if(abs(target) > sum) return 0; //此时没有方案
if((target + sum) % 2 == 1) return 0; //通过解方程可以得到此关系
int bagSize = (target + sum) / 2;
vector<int> dp(bagSize + 1, 0);
dp[0] = 1; //初始化要注意
for(int i = 0; i < nums.size(); i++){
for(int j = bagSize; j >= nums[i]; j--){
dp[j] += dp[j - nums[i]];
}
}
return dp[bagSize];
}
};其实我们需要求的方法总数一直存放在dp[bagSize]里，对于每一次的外层for循环而言，只用dp[bagSize] += dp[bagSize - nums[i]]的这次运算是我们最后将要输出的；而其他格子里的dp[j] += dp[j - nums[i]]的这些运算，也是为了在下一层里做准备。
题目：474.一和零
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
示例 1：
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。 其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
示例 2：
- 输入：strs = ["10", "0", "1"], m = 1, n = 1
- 输出：2
- 解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
提示：
- 1 <= strs.length <= 600
- 1 <= strs[i].length <= 100
- strs[i] 仅由 '0' 和 '1' 组成
- 1 <= m, n <= 100
本题背包变为了两个维度：重量a和重量b。需要定义二维dp数组。
1.dp[i][j]数组含义：尽量装满容量为i、j的背包，有 dp[i][j]这么多个物品
最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
2.递推公式：dp[i][j] = max(dp[i][j], dp[i - x][j - y] + 1);
3.初始化：都初始化为0
4.遍历顺序：先字符从前到后，在背包，背包两个维度都是从后向前。
5.打印dp
代码如下：
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(101, vector<int>(101, 0));
for(string str : strs){
int x = 0;
int y = 0;
for(char c : str){
if(c == '0') x++;
if(c == '1') y++;
}
for(int i = m; i >= x; i--){
for(int j = n; j >= y; j--){
dp[i][j] = max(dp[i][j], dp[i - x][j - y] + 1);
}
}
}
return dp[m][n];
}
};总结一下：
纯背包：给定背包容量，装满这个背包的最大价值
分割等和子集：给定背包容量，能不能装满这个背包？
最后一块石头的重量：给出背包最大重量，尽可能装，问最大能装多少
目标和：给定背包容量，问有多少种方式能装满
一零和：给定背包容量（二维），尽量装满背包有多少个物品
