【动态规划】代码随想录算法训练营第四十四天 |完全背包，518. 零钱兑换 II ， 377. 组合总和 Ⅳ （待补充）

深碍√TFBOYSˉ_ 2024-04-23 04:28 89阅读 0赞

## 完全背包理论基础 ##

#### 完全背包 ####

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight\[i\]，得到的价值是value\[i\] 。**每件物品都有无限个（也就是可以放入背包多次）**，求解将哪些物品装入背包里物品价值总和最大。

**完全背包和01背包问题唯一不同的地方就是，每种物品有无限件**。

同样leetcode上没有纯完全背包问题，都是需要完全背包的各种应用，需要转化成完全背包问题，所以我这里还是以纯完全背包问题进行讲解理论和原理。

在下面的讲解中，我依然举这个例子：

背包最大重量为4。

物品为：

**每件商品都有无限个！**

问背包能背的物品最大价值是多少？

01背包和完全背包唯一不同就是体现在遍历顺序上，所以本文就不去做动规五部曲了，我们直接针对遍历顺序经行分析！

关于01背包我如下两篇已经进行深入分析了：

*  [动态规划：关于01背包问题，你该了解这些！(opens new window)][01_opens new window]
 *  [动态规划：关于01背包问题，你该了解这些！（滚动数组）(opens new window)][01_opens new window 1]

首先再回顾一下01背包的核心代码

for(int i = 0; i < weight.size(); i++) { // 遍历物品
 for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
 }
 }

我们知道01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。

而完全背包的物品是可以添加多次的，所以要从小到大去遍历，即：

// 先遍历物品，再遍历背包
 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]);
 
 }
 }

至于为什么，我在[动态规划：关于01背包问题，你该了解这些！（滚动数组）(opens new window)][01_opens new window 1]中也做了讲解。

dp状态图如下：

![20230724024159.png_origin_url_https_3A_2F_2Fcdn.nlark.com_2Fyuque_2F0_2F2024_2Fjpeg_2F35031166_2F1710077419047-c6f8620b-113b-4e58-baf9-7fff365bb9a5.jpeg_pos_id_ZapO4Y5G][]

相信很多同学看网上的文章，关于完全背包介绍基本就到为止了。

**其实还有一个很重要的问题，为什么遍历物品在外层循环，遍历背包容量在内层循环？**

这个问题很多题解关于这里都是轻描淡写就略过了，大家都默认 遍历物品在外层，遍历背包容量在内层，好像本应该如此一样，那么为什么呢？

难道就不能遍历背包容量在外层，遍历物品在内层？

看过这两篇的话：

就知道了，01背包中二维dp数组的两个for遍历的先后循序是可以颠倒了，一维dp数组的两个for循环先后循序一定是先遍历物品，再遍历背包容量。

**在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的！**

因为dp\[j\] 是根据 下标j之前所对应的dp\[j\]计算出来的。 只要保证下标j之前的dp\[j\]都是经过计算的就可以了。

遍历物品在外层循环，遍历背包容量在内层循环，状态如图：

![20230724024159.png_origin_url_https_3A_2F_2Fcdn.nlark.com_2Fyuque_2F0_2F2024_2Fjpeg_2F35031166_2F1710077418033-7530d69d-da87-4714-a9f4-f065c6ab787a.jpeg_pos_id_yEZFOcFU][]

遍历背包容量在外层循环，遍历物品在内层循环，状态如图：

![20230724024159.png_origin_url_https_3A_2F_2Fcdn.nlark.com_2Fyuque_2F0_2F2024_2Fpng_2F35031166_2F1710077418068-0485cf6f-cf20-45e7-95a3-e63b2f9293a2.png_pos_id_yBntyo7n][]

看了这两个图，大家就会理解，完全背包中，两个for循环的先后循序，都不影响计算dp\[j\]所需要的值（这个值就是下标j之前所对应的dp\[j\]）。

先遍历背包在遍历物品，代码如下：

// 先遍历背包，再遍历物品
 for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
 for(int i = 0; i < weight.size(); i++) { // 遍历物品
 if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
 }
 cout << endl;
 }

完整的C++测试代码如下：

// 先遍历物品，在遍历背包
 void test_CompletePack() {
 vector<int> weight = {1, 3, 4};
 vector<int> value = {15, 20, 30};
 int bagWeight = 4;
 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]);
 }
 }
 cout << dp[bagWeight] << endl;
 }
 int main() {
 test_CompletePack();
 }

// 先遍历背包，再遍历物品
 void test_CompletePack() {
 vector<int> weight = {1, 3, 4};
 vector<int> value = {15, 20, 30};
 int bagWeight = 4;
 
 vector<int> dp(bagWeight + 1, 0);
 
 for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
 for(int i = 0; i < weight.size(); i++) { // 遍历物品
 if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
 }
 }
 cout << dp[bagWeight] << endl;
 }
 int main() {
 test_CompletePack();
 }

本题力扣上没有原题，大家可以去[卡码网第52题(opens new window)][52_opens new window]去练习，题意是一样的，C++代码如下：

#include <iostream>
 #include <vector>
 using namespace std;
 
 // 先遍历背包，再遍历物品
 void test_CompletePack(vector<int> weight, vector<int> value, int bagWeight) {
 
 vector<int> dp(bagWeight + 1, 0);
 
 for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
 for(int i = 0; i < weight.size(); i++) { // 遍历物品
 if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
 }
 }
 cout << dp[bagWeight] << endl;
 }
 int main() {
 int N, V;
 cin >> N >> V;
 vector<int> weight;
 vector<int> value;
 for (int i = 0; i < N; i++) {
 int w;
 int v;
 cin >> w >> v;
 weight.push_back(w);
 value.push_back(v);
 }
 test_CompletePack(weight, value, V);
 return 0;
 }

### [\#][Link 1]总结 ###

细心的同学可能发现，**全文我说的都是对于纯完全背包问题，其for循环的先后循环是可以颠倒的！**

但如果题目稍稍有点变化，就会体现在遍历顺序上。

如果问装满背包有几种方式的话？ 那么两个for循环的先后顺序就有很大区别了，而leetcode上的题目都是这种稍有变化的类型。

这个区别，我将在后面讲解具体leetcode题目中给大家介绍，因为这块如果不结合具题目，单纯的介绍原理估计很多同学会越看越懵！

别急，下一篇就是了！

最后，**又可以出一道面试题了，就是纯完全背包，要求先用二维dp数组实现，然后再用一维dp数组实现，最后再问，两个for循环的先后是否可以颠倒？为什么？** 这个简单的完全背包问题，估计就可以难住不少候选人了。

## 518.零钱兑换II ##

1、题目链接：[. - 力扣（LeetCode）][. - _LeetCode]

2、文章讲解：[代码随想录][Link 2]

3、题目：

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例 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 位符号整数

4、视频链接：

[动态规划之完全背包，装满背包有多少种方法？组合与排列有讲究！| LeetCode：518.零钱兑换II\_哔哩哔哩\_bilibili][LeetCode_518._II_bilibili]

class Solution {
 public int change(int amount, int[] coins) {
 //递推表达式
 int[] dp = new int[amount + 1];
 //初始化dp数组，表示金额为0时只有一种情况，也就是什么都不装
 dp[0] = 1;
 for (int i = 0; i < coins.length; i++) {
 for (int j = coins[i]; j <= amount; j++) {
 dp[j] += dp[j - coins[i]];
 }
 }
 return dp[amount];
 }
 }

## 377. 组合总和 Ⅳ ##

1、题目链接：[. - 力扣（LeetCode）][. - _LeetCode 1]

2、文章讲解：[代码随想录][Link 3]

3、题目：

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:

*  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。

4、视频链接：

[动态规划之完全背包，装满背包有几种方法？求排列数？| LeetCode：377.组合总和IV\_哔哩哔哩\_bilibili][LeetCode_377._IV_bilibili]

class Solution {
 public int combinationSum4(int[] nums, int target) {
 int[] dp = new int[target + 1];
 dp[0] = 1;
 for (int i = 0; i <= target; i++) {
 for (int j = 0; j < nums.length; j++) {
 if (i >= nums[j]) {
 dp[i] += dp[i - nums[j]];
 }
 }
 }
 return dp[target];
 }
 }

[01_opens new window]: https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html
[01_opens new window 1]: https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-2.html
[20230724024159.png_origin_url_https_3A_2F_2Fcdn.nlark.com_2Fyuque_2F0_2F2024_2Fjpeg_2F35031166_2F1710077419047-c6f8620b-113b-4e58-baf9-7fff365bb9a5.jpeg_pos_id_ZapO4Y5G]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/30bee083aedb44e1aa06b2ac9eda2b21.png
[20230724024159.png_origin_url_https_3A_2F_2Fcdn.nlark.com_2Fyuque_2F0_2F2024_2Fjpeg_2F35031166_2F1710077418033-7530d69d-da87-4714-a9f4-f065c6ab787a.jpeg_pos_id_yEZFOcFU]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/e3f78e4366c041308d00f2d3fb155941.png
[20230724024159.png_origin_url_https_3A_2F_2Fcdn.nlark.com_2Fyuque_2F0_2F2024_2Fpng_2F35031166_2F1710077418068-0485cf6f-cf20-45e7-95a3-e63b2f9293a2.png_pos_id_yBntyo7n]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/7d92f9966ebb4871a86e43206ef61dc3.png
[52_opens new window]: https://kamacoder.com/problempage.php?pid=1052
[Link 1]: https://www.programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85.html#%E6%80%BB%E7%BB%93
[. - _LeetCode]: https://leetcode.cn/problems/coin-change-ii/
[Link 2]: https://www.programmercarl.com/0518.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2II.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[LeetCode_518._II_bilibili]: https://www.bilibili.com/video/BV1KM411k75j/
[. - _LeetCode 1]: https://leetcode.cn/problems/combination-sum-iv/
[Link 3]: https://www.programmercarl.com/0377.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C%E2%85%A3.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[LeetCode_377._IV_bilibili]: https://www.bilibili.com/video/BV1V14y1n7B6/