1.什么是完全背包？
有 N 件物品和一个最多能背重量为 W 的背包，第 i 件物品的重量是 weight[i] ，得到的价值是 value[i] 。每件物品都有无限个（可以放入背包多次），求解将哪些物品装入背包里价值总和最大，最大价值是多少。
2.和01背包的区别在哪里
01背包和完全背包唯一的不同就是在遍历顺序上，我们先看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]);
}
}
3.完全背包中的组合数和排列数
对于完全背包问题，有一个很重要的问题：为什么遍历物品在外层，遍历背包容量在内层？在01背包问题中，二维数组先遍历物品还是先遍历背包容量是无所谓的（一维数组必须先遍历物品，再遍历容量），可以颠倒。
在纯完全背包问题中，对于一维 dp 数组而言，两个 for 循环的嵌套顺序其实也是无所谓的，因为 dp[j] 是根据下标 j 之前所对应的 dp[j] 计算出来的，只要保证下标 j 之前的 dp[j] 都是经过计算的即可。
// 先遍历物品
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]);
}
}
// 先遍历背包容量
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]);
}
}
}
但是当题目要求完全背包背景下装满背包有几种方式的话，两个 for 循环的先后顺序就有很大区别了，我们以下面的题目为例子：
零钱兑换Ⅱ
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 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
提示：
1 <= coins.length <= 3001 <= coins[i] <= 5000coins中的所有值 互不相同0 <= amount <= 5000
思路
看到钱币数量不限，就可以判断这是一个完全背包问题。但是和纯完全背包不同，纯完全背包是求凑成背包最大价值是多少，而本题求的是凑成总金额的物品组合个数。
为什么是组合数？这是因为题目说明了 5 = 2 + 2 + 1 和 5 = 2 + 1 + 2 是同一种情况，并不强调元素之间的顺序，所以是组合数。
这里直接说结论，如果题目求的是组合数，我们必须外层遍历物品，内层遍历背包容量；如果题目求的是排列数，我们必须外层遍历背包容量，内层遍历物品。下面来说明这个结论的正确性。
- 我们先看外层遍历物品，内层遍历容量的情况
for (int i = 0; i < coins.size(); ++i) { // 物品
for (int j = coins[i]; j <= amount; ++j) { // 容量
dp[j] += dp[j-coins[i]];
}
}
假设 coins[0] = 1 ，coins[1] = 5 ，那么就先把 1 加入计算，然后把 5 加入计算，得到的方法数量只有 {1, 5} 这种情况，不会出现 {5, 1} 这种情况，所以这种遍历顺序计算的是组合数。
- 再来看外层遍历容量，内层遍历物品的情况
for (int j = 0; j <= amount; ++j) { // 容量
for (int i = 0; i < coins.size(); ++i) { // 物品
if (j - coins[i] >= 0) {
dp[j] += dp[j-coins[i]];
}
}
}
背包容量里的每一个值，都是经过 1 和 5 的计算，包含了 {1, 5} 和 {5, 1} 两种情况，此时计算出来的就是排列数。
最终代码如下：
class Solution {
public:
int change(int amount, vector<int>& coins) {
int ans = 0;
int dp[5005] = {1}; //dp[i]表示凑到i元的方案数
for (int i = 0; i < coins.size(); i++)
for (int j = coins[i]; j <= amount; j++) {
dp[j] = dp[j - coins[i]] + dp[j];
}
return dp[amount];
}
};
4.多重背包扩展
什么是多重背包？
有 N 种物品和一个容量为 V 的背包，第 i 种物品最多有 Mi 件可用，每件消耗的空间是 Ci ，价值是 Wi 。求解将哪些物品装入背包可以在这些物品消耗的空间总和不超过背包容量，且价值总和最大。
如何思考？
多重背包和01背包其实很像，每件物品最多有 Mi 件可用，我们就把 Mi 件摊开，这就是一个01背包问题了。举个例子：
背包最大容量为 10 ，物品如下
| 物品名称 | 重量 | 价值 | 数量 |
|---|---|---|---|
| 物品0 | 1 | 15 | 2 |
| 物品1 | 3 | 20 | 3 |
| 物品2 | 4 | 30 | 2 |
问背包能背的最大价值是多少？
上面的问题就是多重背包问题，我们直接将叠加的相同物品展开，得到下列情况：
| 物品名称 | 重量 | 价值 | 数量 |
|---|---|---|---|
| 物品0 | 1 | 15 | 1 |
| 物品0 | 1 | 15 | 1 |
| 物品1 | 3 | 20 | 1 |
| 物品1 | 3 | 20 | 1 |
| 物品1 | 3 | 20 | 1 |
| 物品2 | 4 | 30 | 1 |
| 物品2 | 4 | 30 | 1 |
这样，多重背包就转换成了一个01背包，且每个物品只用一次。
多重背包有如下代码实现：
void test_multi_pack() {
vector<int> weight = {1, 3, 4};
vector<int> value = {15, 20, 30};
vector<int> nums = {2, 3, 2};
int begWeight = 10;
for (int i = 0; i < nums.size(); ++i) {
while (nums[i] > 1) { // 展开背包
weight.push_back(weight[i]);
value.push_back(value[i]);
nums[i]--;
}
}
vector<int> dp(bagWeight+1, 0);
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]);
}
}
cout << dp[bagWeight] << endl;
}
int main() {
test_multi_pack();
return 0;
}
5.背包问题常见递推公式
- 问能否装满背包（或者最多能装多少）
dp[j] = max(dp[j], dp[j-nums[i]] + nums[i]);
- 问装满背包有几种方法
dp[j] += dp[j-nums[i]];
- 问背包装满的最大价值
dp[j] = max(dp[j], dp[j-weight[i]] + value[i]);
- 问装满背包所有物品的最小个数
dp[j] = min(dp[j-coins[i]] + 1, dp[j]);