1049. 最后一块石头的重量 II

题目链接：1049. 最后一块石头的重量 II
石头相撞，得到最小重量 -> 分成重量近似的两堆 -> 得到结果

分成重量近似的两堆可以用 01背包来求得（同理于416.分割等和子集）

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, 0);for (auto& stone : stones) {//因为weight[i]等于value[i]，所以才可以这么写for (int j = target; j >= stone; --j) {dp[j] = max(dp[j], dp[j - stone] + stone);}}return sum - 2 * dp.back();}
};

sum - 2 * dp.back();

其中，dp[j] 的意思是表示容量为 j 的背包的最大重量，dp.back() 为一堆中最大重量，则另一部分的重量为 sum - dp.back()，由于 sum / 2 是向下取整，因此 sum - dp.back() 大于等于 dp.back()。因此最终结果为 (sum - dp.back()) - dp.back()。

---

494. 目标和

题目链接：494. 目标和
分出加法和减法两个集合 -> 整个集合中，可以分出多少个加法（减法）-> 加法属于背包，集合属于物品（01背包问题）

如有 nums : [1, 1, 1, 1, 1]
dp[j]：装满容量为 j 有 dp[j] 种方法

递推公式：根据每一个状态来确定 dp[j] 有多少种方法，状态为 dp[j - nums[i]]，因为 j 是所对应的容量，每个 j - nums[i] 是剩下的容量，一直递归到从 dp[0] 开始。最终求和得到公式为dp[5] = dp[0] + ... + dp[4] 也就是 dp[j] += dp[j - nums[i]]。
这个递推公式 dp[j] += dp[j - nums[i]] 不与01背包的滚动数组 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]) 完全一样，是因为 dp 公式表示的是多少种方法。

初始化：dp[0] = 1，有一种方法。 服务于递推公式。

对于题意来说，如何求出加法集合中的元素。

集合为 $a,b,c,d$，有如下公式：
$$\begin{array}{rl}(a+b+c+d)& =sum\\ (a+b+c-d)& =target\end{array}$$
根据上述公式，有$(sum+target)/2$ 可以求出加法集合的和。当然，$(sum-target)/2$可以求出减法集合的和。

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = accumulate(nums.begin(), nums.end(), 0);if (abs(target) > sum/*target超过sum*/ || (sum + target) % 2 == 1/*sum、target和不能被2整除，表示不存在*/) return 0;vector<int> dp{1};dp.resize((sum + target) / 2 + 1);for (int i = 0; i < nums.size(); ++i) {for (int j = (sum + target) / 2; j >= nums[i]; --j) {dp[j] += dp[j - nums[i]];}}return dp.back();}
};

---

474.一和零

题目链接：474.一和零
背包为有 m 个 0，n 个 1。物品为各个子集。
与一般的01背包的不同之处为：通常的01背包的物体只有一个属性，就是weight。这个物体有两个属性：0 的个数和 1 的个数。

二维 dp 数组 dp[i][j]，表示三个信息：装满 i个 0，j 个 1 最多需要 dp[i][j]个子集（根据题目所求来表示）

递推公式：dp[i][j] = max(dp[i][j], dp[i - x][j - y] + 1)，x个 0和 y 个 1 表示物品的属性。+1 的 1 相当于value。

初始化：dp[0][0] = 0

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));for (auto& str: strs) {//计算每个物品的属性int x = count(str.begin(), str.end(), '0');int y = str.size() - x;for (int i = m; i >= x; --i) {//0for (int j = n; j >= y; --j) {//1dp[i][j] = max(dp[i][j], dp[i - x][j - y] + 1);}}}return dp.back().back();}
};

---