Day44
- 完全背包
- 518. 零钱兑换 II
- 377. 组合总和 Ⅳ
完全背包
与01背包的区别是一个物品可以取多次。也就是遍历顺序不同,因为可以使用无数次,因此对于背包的循环使用正序遍历。
先遍历物品还是先遍历背包,具体问题具体分析。
如果求组合数就是外层for循环遍历物品,内层for遍历背包。
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]);
}
}
如果求排列数就是外层for遍历背包,内层for循环遍历物品。
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
for(int i = 0; i < weight.size(); i++) { // 遍历物品
if (j - weight[i] >= 0)
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
为什么第二段代码会有一个if
判断语句,是因为内部for
为遍历i
,而不是遍历j
。上述两种区别,可以通过打印一下dp
数组来确认具体功能实现。
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.back() << endl;
}
518. 零钱兑换 II
题目链接:518. 零钱兑换 II
首先,是完全背包类问题;其次,求得是多少种,因此递推公式为dp[j] += dp[j - coins[i]]
,且初始化dp[0] = 1
有一种。
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp{1};
dp.resize(amount + 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.back();
}
};
377. 组合总和 Ⅳ
题目链接:377. 组合总和 Ⅳ
因为求的是排列,因此要先遍历背包,再遍历物品
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<unsigned/*满足测试样例*/> dp{1};
dp.resize(target + 1);
for (int j = 0; j <= target; ++j) {
for (int i = 0; i < nums.size(); ++i) {
if (j - nums[i] >= 0)
dp[j] += dp[j - nums[i]];
}
}
return dp.back();
}
};