K52. 完全背包
代码随想录
1. 思路
（1）dp数组定义以及更新模式
完全背包和01背包的区别可以从展开的二维背包中看出来：
01背包：
dp[i][j] = max(dp[i - 1][j], dp[i-1][j - weights[i - 1]] + values[i - 1])
完全背包：
dp[i][j] = max(dp[i - 1][j], dp[i][j - weights[i - 1]] + values[i - 1])
区别就在i-1上。在保持原状不变的情况下，结论是一样的。但是，在放入第i-1个物品的情况下，如果是01背包，则这个物品是唯一的，所以要退回i-1这一行，寻找最优。但在完全背包的情况下，由于这个物品并非唯一，所以要在第i行寻找。
相当于，在完全背包的情况下，两种分类变成了，不放入这个物品，以及放入1-无穷个这个物品，分别的取值进行比较。
（2）dp数组的压缩以及遍历方式
如果将二维数组压缩成一维数组，在01背包的情况下，由于是i-1到i的映射，每一次更新需要这个位置保持上一轮不变。因此，[j - weights[i - 1]]不能被覆盖，要从后向前遍历。如果是完全背包，存在本轮次i到i的映射，相当于在本轮次，j的值取决于[j - weights[i - 1]]的值，要从前到后遍历。
理解一下，在01背包中，每一轮j的遍历，相当于从i-1的状态下更新，也就是说第i个物品只能用一次，而在完全背包中，每一轮j的遍历，第i个物品可以多次叠加，在限制扩大的时候，可以存在多次累加的情况，因此要从i状态更新。
（3）一维dp数组的ij遍历顺序
在01背包中，每个元素的位置取决于上一个物品j-weight[i]的位置，所以必须先i再j。
在完全背包中，元素的个数可以叠加，因此都是从前到后的状态，没有保留前置位置的需求，因此先i和j的遍历顺序无关紧要。
// 先遍历物品，在遍历背包
void test_CompletePack() {
vector
vector
int bagWeight = 4;
vector
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. 零钱兑换
代码随想录
1. 思路
这道题是很典型的完全背包，只不过最优化目标改编成了累加个数。借鉴之前的结论，dp数组更新逻辑为：
dp[j] += dp[j - coins[i]];
但是，注意i和j的遍历顺序不能变，必须是先i后j。这是因为这道题的要求是排列个数，也就是说顺序不同的算作一种。如果先遍历背包，则会出现15和51两种情况。因此，一定要在外侧循环遍历元素，致使元素呈现顺序排列，去重。
class Solution {
public:
int change(int amount, vector
vector
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];
}
};
377. 组合总和4
代码随想录
1. 解法
这道题和上一题的唯一区别为，求解的是排列，因此，15和51是两种。因此，遍历顺序应该为：
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
class Solution {
public:
int combinationSum4(vector
vector
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];
}
};
精彩文章
发表评论