代码随想录算法训练营 —第四十四天

本文介绍: 完全背包和01背包的区别在于完全背包里的物品能无限次使用，01背包只能用一次。本题是纯完全背包的使用。可以看一看和01背包的区别。本题是对完全背包的场景应用题，在本题与下一题我们将会了解如果求组合数（无需排序）就是外层for循环遍历物品，内层for遍历背包。如果求排列数（需要排序）就是外层for遍历背包，内层for循环遍历物品。先看本题，动态规划五部曲1.确定dp 数组的含义和下标 dp[j]:表示当金额为j时，所需硬币有几种组合2.确定递归公式3.确定dp 数组的初始化 dp[0] = 1;

今天开始《动态规划：完全背包》的学习！

前言：

完全背包和01背包的区别在于完全背包里的物品能无限次使用，01背包只能用一次。

第一题：

简介：

本题是纯完全背包的使用。可以看一看和01背包的区别。

代码 实现：

#include &lt;iostream&gt;
#include &lt;vector&gt;
using namespace std;
int test_bag(vector&lt;int&gt; weight, vector<int> value, int bagWeight){
      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]);
         }
      }
      return dp.back();
}
int main(){
    vector<int> weight;
    vector<int> value;
    int N,V;
    cin>>N>>V;
    for(int i=0;i<N;i++){
        int w;
        int v;
        cin>>w>>v;
        weight.push_back(w);
        value.push_back(v);
    }
    cout<<test_bag(weight,value,V)<<endl;;
    return 0;
}

第二题：

简介：

本题是对完全背包的场景应用题，在本题与下一题我们将会了解

如果求组合数（无需排序）就是外层for循环遍历物品，内层for遍历背包。

如果求排列数（需要排序）就是外层for遍历背包，内层for循环遍历物品。

先看本题，动态规划五部曲

1.确定dp 数组的含义和下标

dp[j]:表示当金额为j时，所需硬币有几种组合

2.确定递归公式

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

3.确定dp 数组的初始化

dp[0] = 1;

4.遍历数组

5.查看dp数组是否符合要求

代码 实现：

    //dp[j]表示凑成j有几种方式
    int change(int amount, vector<int>&amp; 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.back();
    }

第三题：

简介：

大家通过示例可以看出本题对数组元素的顺序有要求，所以本题是求排列数。

同样，动态规划五部曲

1.确定dp数组的含义及下标

dp[j] 表示数为j时有几种组合方式

2.确定递归公式

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

3.确定dp数组的初始化

dp[0]=1;

4.确定遍历的顺序（注意本题的遍历顺序）

  for(int j=0;j<=target;j++){  // 背包
            for(int i=0;i<nums.size();i++){  //物品
                 if (j - nums[i] >= 0&amp;&amp; dp[j] < INT_MAX - dp[j - nums[i]])dp[j] +=dp[j-nums[i]];
            }
            for(int i=0;i<dp.size();i++){
            cout<<dp[i]<<"  ";
            }
            cout<<endl;
        }

个数可以不限使用，说明这是一个完全背包。

得到的集合是排列，说明需要考虑元素之间的顺序。

本题要求的是排列，那么这个for循环嵌套的顺序可以有说法了。

在上一题中就已经讲过了。

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

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

如果把遍历nums（物品）放在外循环，遍历target的作为内循环的话，举一个例子：计算dp[4]的时候，结果集只有 {1,3} 这样的集合，不会有{3,1}这样的集合，因为nums遍历放在外层，3只能出现在1后面！

所以本题遍历顺序最终遍历顺序：target（背包）放在外循环，将nums（物品）放在内循环，内循环从前到后遍历。

5.确定dp数组符合要求

代码 实现：

  int combinationSum4(vector<int>&amp; nums, int target) {
        vector<int> dp(target+1,0);
        dp[0]=1;
        for(int j=0;j<=target;j++){  // 背包
            for(int i=0;i<nums.size();i++){  //物品
                 if (j - nums[i] >= 0&amp;&amp; dp[j] < INT_MAX - dp[j - nums[i]])dp[j] +=dp[j-nums[i]];
            }
            for(int i=0;i<dp.size();i++){
            cout<<dp[i]<<"  ";
            }
            cout<<endl;
        }
        return dp.back();
    }