01背包问题

问题

有 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(列)。