当前位置:   article > 正文

Day 44 动态规划 6

Day 44 动态规划 6

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的遍历顺序无关紧要。

  1. // 先遍历物品,在遍历背包
  2. void test_CompletePack() {
  3. vector<int> weight = {1, 3, 4};
  4. vector<int> value = {15, 20, 30};
  5. int bagWeight = 4;
  6. vector<int> dp(bagWeight + 1, 0);
  7. for(int i = 0; i < weight.size(); i++) { // 遍历物品
  8. for(int j = weight[i]; j <= bagWeight; j++) { // 遍历背包容量
  9. dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  10. }
  11. }
  12. cout << dp[bagWeight] << endl;
  13. }
  14. int main() {
  15. test_CompletePack();
  16. }

518. 零钱兑换

代码随想录

 1. 思路

这道题是很典型的完全背包,只不过最优化目标改编成了累加个数。借鉴之前的结论,dp数组更新逻辑为:

dp[j] += dp[j - coins[i]];

但是,注意i和j的遍历顺序不能变,必须是先i后j。这是因为这道题的要求是排列个数,也就是说顺序不同的算作一种。如果先遍历背包,则会出现15和51两种情况。因此,一定要在外侧循环遍历元素,致使元素呈现顺序排列,去重。

  1. class Solution {
  2. public:
  3. int change(int amount, vector<int>& coins) {
  4. vector<int> dp(amount + 1, 0);
  5. dp[0] = 1;
  6. for (int i = 0; i < coins.size(); i++) { // 遍历物品
  7. for (int j = coins[i]; j <= amount; j++) { // 遍历背包
  8. dp[j] += dp[j - coins[i]];
  9. }
  10. }
  11. return dp[amount];
  12. }
  13. };

377. 组合总和4

代码随想录

1. 解法

这道题和上一题的唯一区别为,求解的是排列,因此,15和51是两种。因此,遍历顺序应该为:

如果求组合数就是外层for循环遍历物品,内层for遍历背包

如果求排列数就是外层for遍历背包,内层for循环遍历物品

  1. class Solution {
  2. public:
  3. int combinationSum4(vector<int>& nums, int target) {
  4. vector<int> dp(target + 1, 0);
  5. dp[0] = 1;
  6. for (int i = 0; i <= target; i++) { // 遍历背包
  7. for (int j = 0; j < nums.size(); j++) { // 遍历物品
  8. if (i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]]) {
  9. dp[i] += dp[i - nums[j]];
  10. }
  11. }
  12. }
  13. return dp[target];
  14. }
  15. };

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小丑西瓜9/article/detail/350381
推荐阅读
相关标签
  

闽ICP备14008679号