416. 分割等和子集
力扣题目链接
本题中每一个元素的数值既是重量，也是价值。
dp[j]表示 背包总容量（所能装的总重量）是j，放进物品后，背的最大重量为dp[j]
如果背包容量为target， dp[target]就是装满 背包之后的重量，所以 当 dp[target] == target 的时候，背包就装满了。
本题，相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。
所以递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
类比背包问题 每个数质量与价值一样
外层循环是遍历每个物品，内层循环是遍历背包容量
j>=nums[i]当前背包容量一定要大于当前物品重量
max 没放物品就是dp[j] 放物品了就是dp[j-nums[i]]+nums[i] 当前背包容量减去当前物品重量加上当前物品价值。
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--) { // 每一个元素一定是不可重复放入，所以从大到小遍历
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
// 集合中的元素正好可以凑成总和target
if (dp[target] == target) return true;
return false;
}
};1049.最后一块石头的重量II
力扣题目链接(opens new window)
那么分成两堆石头，一堆石头的总重量是dp[target]，另一堆就是sum - dp[target]。
在计算target的时候，target = sum / 2 因为是向下取整，所以sum - dp[target] 一定是大于等于dp[target]的。
那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]。
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
vector<int> dp(15001, 0);
int sum = 0;
for (int i = 0; i < stones.size(); i++) sum += stones[i];
int target = sum / 2;
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.目标和
力扣题目链接
我们可以把数组中所有取正号的元素看作一个集合P，所有取负号的元素看作一个集合N。那么有：
sum(P) - sum(N) = target
sum(P) + sum(N) = sum(nums)
两式相加得：
sum(P) = (target + sum(nums)) / 2
也就是说，我们只需要找到有多少种方法可以从数组中选出若干个元素使得它们的和等于(target + sum(nums)) / 2即可。这就变成了一个经典的01背包问题。
所以我们可以把状态定义为dp【j】，表示用数组中若干个元素组成和为j的方案数。那么状态转移方程就是：
dp【j】 = dp【j】 + dp[j - nums【i】]
这个方程的意思是，如果我们要用若干个元素组成和为j的方案数，那么有两种选择：不选第i个元素或者选第i个元素。如果不选第i个元素，那么原来已经有多少种方案数就不变；如果选第i个元素，那么剩下要组成和为j - nums【i】 的方案数就等于dp[j - nums【i】]。所以两种选择相加就是dp【j】。
但是在实现这个状态转移方程时，有一个细节需要注意：由于每次更新dp【j】都依赖于之前计算过得dp值（也就是说当前行依赖于上一行），所以我们必须从后往前遍历更新dp值（也就是说从右往左更新），否则会覆盖掉之前需要用到得值。
最后返回dp【bag_size】即可。
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int sum = 0;
for (int i = 0; i < nums.size(); i++) sum += nums[i];
if (abs(S) > sum) return 0; // 此时没有方案
if ((S + sum) % 2 == 1) return 0; // 此时没有方案
int bagSize = (S + 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];
}
};
