本文主要是介绍代码随想录算法训练营第day44|完全背包、518. 零钱兑换 II 、377. 组合总和 Ⅳ，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
完全背包
518.零钱兑换II
377. 组合总和 Ⅳ
完全背包
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
- 在01背包，为了防止物品被多次加入背包，一维数组遍历时要把物品放在外循环，背包容量放在内循环；
- 在纯完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的！
- 在01背包，为了防止物品被多次加入背包，遍历背包时要从大到小倒叙
- 在完全背包中，物品数量不限，可以多次加入，因此从小到大遍历
- 在求排列组合里，递推公式dp[j]+=dp[j-num[i]]，而求组合时，先遍历背包，求排列时，先遍历物品。
518.零钱兑换II
力扣题目链接
(opens new window)
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
- 输入: amount = 5, coins = [1, 2, 5]
- 输出: 4
解释: 有四种方式可以凑成总金额:
- 5=5
- 5=2+2+1
- 5=2+1+1+1
- 5=1+1+1+1+1
示例 2:
- 输入: amount = 3, coins = [2]
- 输出: 0
- 解释: 只用面额2的硬币不能凑成总金额3。
示例 3:
- 输入: amount = 10, coins = [10]
- 输出: 1
注意，你可以假设：
- 0 <= amount (总金额) <= 5000
- 1 <= coin (硬币面额) <= 5000
- 硬币种类不超过 500 种
- 结果符合 32 位符号整数
思路：硬币数不限，完全背包问题，总金额是背包容量，硬币面额相当于物品重量；
问组合数，外层遍历物品，内层遍历背包；
为防止推导结果全0，dp[0]初始化为1
class Solution {
public:int change(int amount, vector<int>& 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[amount];}
};377. 组合总和 Ⅳ
力扣题目链接
(opens new window)
难度：中等
给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
示例:
- nums = [1, 2, 3]
- target = 4
所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)
请注意，顺序不同的序列被视作不同的组合。
因此输出为 7。
完全背包，求排列数，外层遍历物品，内层遍历背包容量，dp[0]初始化为1
class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<int>dp(target+1,0);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]])
//C++测试用例有两个数相加超过int的数据，所以需要在if里加上dp[i] < INT_MAX - dp[i - num]。{ dp[i]+=dp[i-nums[j]];}}}return dp[target];}
};参考：代码随想录
这篇关于代码随想录算法训练营第day44|完全背包、518. 零钱兑换 II 、377. 组合总和 Ⅳ的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
