01背包的应用
- 分割等和子集： 给一个weight的背包，尽量往里塞满，如果有刚刚塞满的组合，则返回true。问的是是否存在刚刚好塞满weight背包的组合。
- 最后一块石头的重量Ⅱ： 给一个weight的背包，尽量往里塞满，若能刚刚塞满，说明最后剩的一块石头重量为0（即不剩了）。
- 目标和：这道题就有所区别了，问的是刚刚好塞满weight背包的组合个数。所以数组中dp[i] [j]的含义就不能像上两道题一样，定义为将物品[0 - i]放入容量为j的背包中的最大价值。而是，dp[i] [j]代表将物品[0 - i]放入容量为 j 的背包中，刚好装满的方法种数。
纯01背包：装满背包的最大价值
分割等和子集： 是否能装满背包
最后一块石头的重量Ⅱ：一个背包最多能装多少件物品
目标和：刚好装满背包有多少种方法
一和零：装满这个背包最多用多少个物品
前三题，递推公式都是dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
LC494. 目标和
本题关键是，找到与背包问题关联出。
- 假设将所有的数分为两堆，一堆是正号，一堆是负号
- 由left - right = target，left + right = sum，推出left = (target + sum) / 2;
- 所以可以将left作为背包的weight，每个数字的重量大小即为它的价值大小
1、dp[i] [j]含义：将物品[0 - i]放入容量为 j 的背包中，刚好装满的方法种数
2、递推公式：类似“爬楼梯”和“不同路径”的思想。如一个背包weight为5，那对于一个重量为2的物品，用它来刚刚装满weight = 5的方法种数应该为dp[i] [3]。简单来讲，就是现在如果有一个物体重量为2，那有dp[3]种方法可以，刚好凑成dp[5]。
-
举个例子，现在有分别为1，2，3，4，5的物品，问刚好装满weight = 5背包的方法数
- 对1物品，即有dp[4]种方法凑成dp[5]
- 对2物品，即有dp[3]种方法凑成dp[5]
- 对3物品，即有dp[2]种方法凑成dp[5]
- 对4物品，即有dp[1]种方法凑成dp[5]
- 对5物品，即有dp[0]种方法凑成dp[5]
所以有dp[5] = dp[4] + dp[3] + dp[2] + dp[1] + dp[0]
抽象上述公式，即推出了求解要刚好装好背包方法数的一条通用公式：
dp[j] += dp[j - nums[i]]
3、dp数组初始化：dp[0]应该初始化为1，非0下标的其他数组元素初始化为0即可
- 如例子：[0]，target = 0，此时装满weight = 0的背包，应该有1中方法
- 如例子：[0,0,0,0,0]，target = 0，开始dp[0] = 1，最后遍历全部元素后，得到的dp[0]应该为32（即2^5），如果一开始dp[0] = 0，那后面每次的dp[0]就真的只能一直为0了
- 若非0下标的数组元素初始化为非0的话，也会影响上述公式中其他下标元素的推导过程
4、遍历顺序：经上述分析，可用01背包的思想去解决本问题，使用一维数组，遍历顺序应该是从右往左。
细节：
- sum + target为奇数 或 target绝对值大于sum 时，不会有解
- 第二个for循环中，为了不让dp数组向左越界，所以 j - nums[i] 需要 >= 0，这个限制在for的条件选项中可以写明，同时意味着当 j < nums[i]时，dp[j]是无需更新的，因此不用处理（“分割等和子集”中自己的写法对这点处理不够好。）
int findTargetSumWays(vector<int>& nums, int target)
{
int size = nums.size();
int sum = 0;
for (int i = 0; i < size; ++i)
{
sum += nums[i];
}
//两者之和为奇数，或者target绝对值大于sum，无解
if ((target + sum) & 1 == 1 || abs(target) > sum)
{
return 0;
}
int weight = (target + sum) >> 1;
int count = 0;
vector<int> dp(weight + 1, 0);
dp[0] = 1;
for (int i = 0; i < size; ++i)
{
for (int j = weight; j >= nums[i]; --j)
{
dp[j] += dp[j - nums[i]];
}
}
return dp[weight];
}
LC1049. 最后一块石头的重量Ⅱ
开始的想法是，取sum / 2为weight，当有物品重量超过weight时，需要取weight = stones[i] - 1；事实证明，自己对石头碰撞的理解还是不够清晰
int lastStoneWeightII(vector<int>& stones)
{
int size = stones.size();
int sum = 0;
for (int i = 0; i < size; ++i)
{
sum += stones[i];
}
int weight = sum / 2;
int overhalf = (int)((float)sum / 2 + 0.5);
for (int i = 0; i < size; ++i)
{
if (stones[i] > weight)
{
weight = stones[i] - 1;
overhalf = stones[i];
}
}
vector<int> dp(weight + 1, 0);
int maxStone = 0;
for (int i = 0; i < size; ++i)
{
for (int j = weight; j >= stones[i]; --j)
{
dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
}
if (dp[weight] > maxStone)
{
maxStone = dp[weight];
}
}
return overhalf - maxStone;
}
开始的做法，导致错误的原因是，sum = 151，取weight = 75，但组合33 + 40 = 73，最后直接用overhalf--76 - 73 = 3的结果是错误的。
正确求最后剩余的石头重量应该是：return sum - dp[weight] - dp[weight]，即151 - 73 - 73 = 5。
LC474. 一和零
需要表示三个变量，分别是1的个数，0的个数，和最多能装多少个物品
所以至少需要二维的dp数组才能表现完三个变量
1、dp[i] [j]含义：背包容量为 i, j 时，最多能装的物品个数
2、递推公式：假设当前的物品重量为x, y，对于该物品放与不放，有两种状态
-
放物品：那此时的最大物品数为dp[i - x] [j - y] + 1
-
不放物品：与原来的一直，dp[i] [j]（没有更新，所以这是一个滚动二维数组）
dp[i] [j] = max(dp[i - x] [j - y] + 1, dp[i] [j])
3、dp数组初始化：滚动二维数组，类似滚动的一维数组，全初始化0即可
4、遍历顺序：3个for循环，第一个是对物品的遍历，从头到尾即可，对二维数组的 i, j 遍历时，类似滚动一维数组，需要倒序遍历刷新物品的最大个数（第一是为了契合公式，不影响其他的元素求值，第二是对于01背包问题的滚动数组需要后序遍历）
int findMaxForm(vector<string>& strs, int m, int n)
{
int size = strs.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int stuff = 0; stuff < size; ++stuff)
{
int x = 0, y = 0;
for (int temp = 0; temp < strs[stuff].size(); ++temp)
{
if (strs[stuff][temp] == '0') ++x;
else ++y;
}
for (int i = m; i >= x; --i)
{
for (int j = n; j >= y; --j)
{
dp[i][j] = max(dp[i - x][j - y] + 1, dp[i][j]);
}
}
}
return dp[m][n];
}