题1：
指路：1049. 最后一块石头的重量 II - 力扣（LeetCode）
思路与代码：
本题中，我们要让剩下的石头重量尽可能小，那么每次就要尽可能找重量相等或最相近的两个石头，如果我们把两个石头分别放入两个数组内，再继续按照重量找尽量相等的石头，此时我们发现，两个数组内的元素和趋于相等，也就是两个数组的元素和尽量等于原数组和的一半，像极了第二题 分割等和子集。与之不同的是需要返回剩下的石头重量。那么我们再顺一遍(注意本题中依旧是石头的重量与价值的意义相同)。尽量将一个子集凑成原数组元素和的一半，一个元素最多取一次，01背包问题。首先，定义一个数组dp[j]，其含义为一个容量为j的背包，所放物品最大的价值是dp[j]；其次，我们确定递推公式，01背包的递推公式是，放物品i的价值和不放物品i的价值的较大值，也就是dp[j]=max(dp[j], dp[j - stones[i]] + stones[i])；然后我们进行初始化，当背包的容量也就是j为0时放不进任何东西，最大价值自然是0，当容量非0时，既要满足常理不为负数，也要保证后面的值不被初始值覆盖，所以也要初始化为0。此处我们假设一个极端情况，当所有的石头共30块重量皆为最大值100，此时原数组总和为最大值3000，但我们求的是一个子集到达原和的一半，所以此处在无溢出的情况下初始为dp(1501, 0)；接着，我们确定遍历顺序，在此处两个for循环，外层遍历物品i，内层j遍历背包(注意，01背包内层顺序为倒序，完全背包内层顺序为正序，)。最后我们打印出结果，这里求的是剩下的重量，我们用其中一堆的重量sum-stones[target]减去另一堆stones[target]的重量即可，也就是sum-stones[target]-stones[target]。代码如下：
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int n = stones.size();
int sum = 0; // stones数组的元素和
for (int i = 0; i < stones.size(); i++) {
sum += stones[i];
}
int target = sum / 2; // 要达到的数
// 定义一个dp数组，容量为j的背包盛放的最大价值(重量)是dp[j]
vector<int>dp (1501, 0);
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]);
}
};题2：
指路：494. 目标和 - 力扣（LeetCode）
思路与代码：
对于这个题，我们将整数和负数分开放，求得原数组的元素和之后，如果原和减去正数和等于target则符合条件。又因为其中的元素只使用一次，归为01背包问题类。首先，定义一个数组dp[j]，其含义为填满j容量的背包，有dp[j]种方法。其次我们确定递推公式，当数值为nums[i]时，则有dp[j-nums[i]]种方法。这里要注意一个特殊情况，当target=5而nums[i]为2时无法得到结果，所以当target+sum与2的余数不为0时没有结果。然后进行初始化，我们将大小为正数个+1的dp数组初始化为0，当j=0时方法为1种。接着确定遍历顺序，依旧是外层物品正序(此处物品是正数)，内层背包倒序(此处为正数个数大小的背包)。最后打印即可。
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 (sum < abs(target)) return 0;
if ((target + sum) % 2 == 1) return 0;
// 例如target=5，nums=2
int t = (target + sum) / 2;
vector<int> dp(t + 1, 0); //
dp[0] = 1;
for (int i = 0; i < nums.size(); i++) { // 物品
for (int j = t; j >= nums[i]; j--) { // 背包
//dp[i][j] = max(dp[i][j], dp[i - 1][j - nums[i]] + nums[i]);
dp[j] += dp[j - nums[i]] ;
}
}
return dp[t];
}
};
