本文主要是介绍代码随想录第44天 | 完全背包 、 518. 零钱兑换 II 、 377. 组合总和 Ⅳ，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、前言
参考文献：代码随想录
今天的主题是动态规划中的完全背包问题，完全背包的与01背包的区别是：
完全背包：可以里面的物品可以使用无数次；
01背包：里面的物品是允许使用一次；
二、完全背包
1、思路：
这里参考的是卡码网的完全背包问题；
首先和动态规划五部曲一摸一样：
（1）确定dp数组：
vector<int> dp(V + 1, 0);这里的dp数组和之前的滚动数组一样，采用的是复制的方法来替代二维数组的存数问题；
而且这里的默认初始化也为0，因为作比较的非负数最小就是0；
（2）递推公式：
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);还是与之前一样的，把dp[j]进行复制，然后再与dp[j - weight[i]] + value[i]]进行比较，选一个最大的；
（3）遍历顺序：
for (int i = 0; i < N; i++) {for (int j = weight[i]; j <= V; j++) {// 3、递推公式dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}}这里就有所区别了首先第一层for循环一样的，只是这里的第二层for循环代表的是从小开始遍历，然后这样的话每一个物品就可以被多次的使用，多次的相加到总价里面了。这里与之前的一个01背包的题目行程了反比；
2、整体代码如下：
#include<iostream>
#include<vector>
using namespace std;int main() {// 输入int N; // 研究材料的种类int V; // 行李空间cin >> N >> V;vector<int> value(N);vector<int> weight(N);for (int i = 0; i < N; i++) {cin >> weight[i] >> value[i];}// 1、创建dp数组vector<int> dp(V + 1, 0); // 默认初始化//2、遍历顺序for (int i = 0; i < N; i++) {for (int j = weight[i]; j <= V; j++) {// 3、递推公式dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}}cout << dp[V] << endl;return 0;
}三、 零钱兑换 II
1、思路：
这里的一维感觉比二维好理解；
还是使用dp五部曲
（1）dp数组的确定：
vector<int> dp(amount + 1, 0);dp代表种数j代表找钱的大小；
（2）初始化：
dp[0] = 1;因为当要找的钱为0时，就 有一种找钱方案，那就是0；
（3）递推公式：
dp[j] += dp[j - coins[i]];这里就是进行重复的元素使用，不是简单的复制，而是累加；（其中包含了去重）
（4）遍历顺序：
for (int i = 0; i < coins.size(); i++) {for (int j = coins[i]; j <= amount; j++) {// 递推公式，当前的种类，加上加上当前面额的方式dp[j] += dp[j - coins[i]]; }}第一层for循环没什么好讲的，第二层就是与完全背包相似了，多次使用相同的元素，从小开始遍历；
2、整体代码如下：
（1）一维：
class Solution {
public:int change(int amount, vector<int>& coins) {// 1、确定dp数组/*用的是完全背包的思路*/// dp数组代表排列的种数// 下标代表容量vector<int> dp(amount + 1, 0);// 找钱为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]]; }}// 打印dp数组// for (auto i : dp) {// cout << i << endl;// }return dp[amount];}
};（2）二维：
class Solution {
public:int change(int amount, vector<int>& coins) {// 1、确定dp数组// 下标代表容量// dp的值代表搭配方案的种数，i代表物品，j代表容量vector<vector<int>> dp(coins.size() + 1, vector<int>(amount + 1, 0));// 找钱为0时，那么就有一种的方式dp[0][0] = 1;// 遍历方式for (int i = 1; i <= coins.size(); i++) {// 初始化dp[i][0] = 1;for (int j = 1; j <= amount; j++) {// 递推公式，当前的种类，加上加上当前面额的方式if (j < coins[i - 1]) {dp[i][j] = dp[i - 1][j];} else {// 这个递推公式很巧妙，当容量超过或者等于当前的零钱时// 就直接加上前一个的种数and装上这个零钱的种数；dp[i][j] = dp[i][j - coins[i - 1]] + dp[i - 1][j];}}}// 打印dp数组for (auto i : dp) {for (auto j : i) {cout << j << " ";}cout << endl;}return dp[coins.size()][amount];}
};四、 组合总和 Ⅳ
1、思路：
这个与找零钱的思路差不多，但是！
有一个重点！就是遍历顺序，在卡哥的文章中提到：
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
这就是终点，解释如下：
如果把遍历nums（物品）放在外循环，遍历target的作为内循环的话，举一个例子：计算dp[4]的时候，结果集只有 {1,3} 这样的集合，不会有{3,1}这样的集合，因为nums遍历放在外层，3只能出现在1后面！
也就是说，当先遍历背包时就会出现数字都是被固定顺序的，但是如果先遍历数字，在确定背包大小就可以有不同的组合出现；
2、整体代码如下：
class Solution {
public:int combinationSum4(vector<int>& nums, int target) {// 1、确定dp数组// dp为种数，j为背包大小// 这里用unsigned是为了避免越界vector<unsigned int> dp(target + 1, 0);// 2、初始化，target为0，则种类有1种dp[0] = 1;// 3、遍历顺序for (int i = 1; i <= target; i++) {for (int j = 0; j < nums.size(); j++) {// 确定大小if (i >= nums[j]) {dp[i] += dp[i - nums[j]];}}}return dp[target];}
};今日学习时间：1.5小时
leave message:
If you are able to appreciate beauty in the ordinary, your life will be more vibrant.
如果你擅长于平凡生活中的美，那么你的生活会更加多姿多彩。
这篇关于代码随想录第44天 | 完全背包 、 518. 零钱兑换 II 、 377. 组合总和 Ⅳ的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
