问题
有 n 件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是
weight[i]，得到的价值是 value[i] 。
每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
| 重量 |
价值 |
|
| 物品0 |
1 |
15 |
| 物品1 |
3 |
20 |
| 物品2 |
4 |
30 |
416. 分割等和子集
判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
优先计算总和，如果是奇数不可能平均分配，返回 false。然后计算出
背包问题中的容量 sum = sum / 2。至于重量和价值就是 nums
中存储的，即重量和价值一致。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public:
bool canPartition(vector<int>& nums) {
auto sum = 0;
for (const auto& num : nums) {
sum += num;
}
if ((sum % 2) != 0) {
return false;
}
sum = sum / 2;
int len = nums.size();
vector<vector<int>> dp(len + 1, vector<int>(sum + 1, 0));
for (int i = 1; i <= len; i++) {
for (int j = 1; j <= sum; j++) {
if (nums[i - 1] > j) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = max(dp[i - 1][j],
dp[i - 1][j - nums[i - 1]] + nums[i - 1]);
}
}
}
return dp[len][sum] == sum;
}
};
|
推演过程：nums = [1,5,11,5]
初始化，在没有物品或者没有空间的情况下，全部初始化为0
| 物品/空间 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
| 没有物品 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| 物品 A |
0 |
|
|
|
|
|
|
|
|
|
|
|
| 物品 B |
0 |
|
|
|
|
|
|
|
|
|
|
|
| 物品 C |
0 |
|
|
|
|
|
|
|
|
|
|
|
| 物品 D |
0 |
|
|
|
|
|
|
|
|
|
|
|
空间不足的情况下，就不能放入新的物品，那就继承前面装入物品价值的结果。
见下面：空间为 1 的情况下，无法放入物品 B，那就继承前面的结果
1，因为放不下物品 B，但能够放下物品 A。
| 物品/空间 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
| 没有物品 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| 物品 A |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
| 物品 B |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
| 物品 C |
0 |
|
|
|
|
|
|
|
|
|
|
|
| 物品 D |
0 |
|
|
|
|
|
|
|
|
|
|
|
空间足够的情况下，有两种选择，一种是选择放下当前物品，另一种是选择不放下当前物品。
为什么会存在这两种选择的情况呢？因为有得必有失，当你选择放下当前物品，那么你的空间会有损失。
见下面：现在你要放入 物品 B，空间大小为
5，明显是可以容下。那究竟选择放还是不放呢？
放：dp[i - 1][j - nums[i - 1]] + nums[i - 1]
不放：dp[i - 1][j]
放入物品的话，首先要取得减去容纳当前物品剩余空间对应的dp，再加上当前物品价值（因为我们已经选择容纳该物品）。
如果没有放入物品，情况就和空间不足类似，继承前面的价值结果。
| 物品/空间 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
| 没有物品 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| 物品 A |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
| 物品 B |
0 |
1 |
1 |
1 |
1 |
5 |
|
|
|
|
|
|
| 物品 C |
0 |
|
|
|
|
|
|
|
|
|
|
|
| 物品 D |
0 |
|
|
|
|
|
|
|
|
|
|
|
1049 最后一块石头的重量 II
为了让这些石头尽可能粉碎，就让选择的那些石头尽可能接近总和的平均值，和上面那道题类似。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
auto sum = 0;
for (const auto& stone : stones) {
sum += stone;
}
int tmp_sum = sum;
sum = sum / 2;
int len = stones.size();
vector<vector<int>> dp(len + 1, vector<int>(sum + 1, 0));
for (int i = 1; i <= len; i++) {
for (int j = 1; j <= sum; j++) {
if (stones[i - 1] > j) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - stones[i - 1]] +
stones[i - 1]);
}
}
}
return tmp_sum - (dp[len][sum] * 2);
}
};
|
返回值特别要注意，由于我们已经计算出能容下的最大价值（重量）A
，因此要用总和 减去 两倍的 A。
两倍的原因是用来相互抵消的缘故。
494. 目标和
这道题有数学关系在里面，我们知道数组里面的元素可以是正数，也可以是负数。
那我们就把 全部的正数视为 a，全部的负数视为
b，得到如下确定的关系式：
1
2
3
4
5
6
| a + b = target
a - b = sum
a = (target + sum) / 2
b = (target - sum) / 2
|
由于 target 和 sum 都会是确定的值，那么 a 和 b 就是确定的。
由于题目说 nums 是正数集合，那么问题就变成 在 nums
中找到一个子集，使得其元素和等于 a。
从 nums 数组中找到组合，这些组合的和为 a。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = 0;
int n = nums.size();
int left = 0,right = 0;
for(int i=0;i<n;i++) {
sum += nums[i];
}
if (abs(target) > sum) return 0;
if ((sum + target) % 2 == 1) return 0;
left = (sum + target) / 2;
vector<vector<int>> dp(n + 1, vector<int>(left + 1));
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= left; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= nums[i-1]) {
dp[i][j] += dp[i - 1][j - nums[i-1]];
}
}
}
return dp[n][left];
}
};
|
在后面得题目中，在求装满背包有几种方法的情况下，递推公式一般为：dp[i][j] += dp[i - 1][j - nums[i-1]]
dp[0][0] = 1 是因为 0(行) 可以组成 0（列）。
