Day44完全背包
By HQWQF 2024/01/29
笔记
完全背包
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
和01背包的区别在每件物品都可以放入背包无数次。
和01背包的区别：遍历顺序
滚动数组版本的01背包的内嵌的循环是从大到小遍历，因为需要利用上一行的结果，找到从背包中去掉当前物品的价值和重量后背包的最大价值。
然而完全背包的背包能装重复装入物品，也就是说在同一行更新了使用当前物品后dp[j - weight[i]]的新值，我们在后面的列中也可以利用这个新值去计算dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
其余和01背包一样。另外，不同于01背包，完全背包的滚动数组版本两个for的顺序是可以更改的。因为完全背包的背包容量遍历从前到后，递推公式依赖的前面的值都是经过处理的。
// 先遍历物品，在遍历背包
void test_CompletePack() {
vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
int bagWeight = 4;
vector<int> dp(bagWeight + 1, 0);
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = weight[i]; j <= bagWeight; j++) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
cout << dp[bagWeight] << endl;
}
int main() {
test_CompletePack();
}
518.零钱兑换II
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
- 输入: amount = 5, coins = [1, 2, 5]
- 输出: 4
解释: 有四种方式可以凑成总金额:
- 5=5
- 5=2+2+1
- 5=2+1+1+1
- 5=1+1+1+1+1
示例 2:
- 输入: amount = 3, coins = [2]
- 输出: 0
- 解释: 只用面额2的硬币不能凑成总金额3。
示例 3:
- 输入: amount = 10, coins = [10]
- 输出: 1
注意，你可以假设：
- 0 <= amount (总金额) <= 5000
- 1 <= coin (硬币面额) <= 5000
- 硬币种类不超过 500 种
- 结果符合 32 位符号整数
动态规划
dp[j]：凑成总金额j的货币组合数为dp[j]
滚动数组版本递推公式：dp[j] += dp[j - coins[i]];
解释：在有货币种类1，2，……且可以新选择货币i时，总金额j的货币组合数dp[j]需要加上凑成j - coins[i]的货币组合数，因为这些组合加上可以新选择货币i时总金额就是j了。
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp(amount + 1, 0);
dp[0] = 1;
for (int i = 0; i < coins.size(); i++) { // 遍历物品
for (int j = coins[i]; j <= amount; j++) { // 遍历背包
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
};
这里值得注意的是，不能调换两个for循环的顺序，因为我们要求的是组合，不能组合重复。
比如coins[0] = 1，coins[1] = 5，在遍历每一列的过程中就无法区分{1, 5} 和 {5, 1}两种情况。
先遍历容量再遍历物品，遍历列，就是在给定容量的背包中，不断尝试加入新的可选物品，不断更新在给定容量背包中的凑数方法数，在这个例子中，当j=6，i=0时和j=6，i=1时，所加的dp[6 - 1]和dp[6 - 5]，其中就有重复，一个是基于选定币值5的情况再选币值1的情况，一个是先选币值1再选币值5，形成组合重复。
为什么先遍历物品再遍历容量就是组合呢，如果遍历每一行，那我们考虑的是在有当前物品及其上面的物品可选择的情况下，在每一背包容量下有几种凑数的方法，遍历每一行时可挑选物品的情况都有所不同，所以会先选币值1后选币值5，不会考虑{5, 1}的情况。
377. 组合总和 Ⅳ
给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
示例:
- nums = [1, 2, 3]
- target = 4
所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)
请注意，顺序不同的序列被视作不同的组合。
因此输出为 7。
动态规划
和上一题对应，由于顺序不同的序列被视作不同的组合，实际上要求的是排列，先遍历背包再遍历物品即可。
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target + 1, 0);
dp[0] = 1;
for (int i = 0; i <= target; i++) { // 遍历背包
for (int j = 0; j < nums.size(); j++) { // 遍历物品
if (i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]]) {
dp[i] += dp[i - nums[j]];
}
}
}
return dp[target];
}
};