完全背包问题

基本概念

背包问题是动态规划中的一个经典分支，典型的背包问题就是给定一个有容量上限的背包，再给定一系列的物品，每个物品都有其重量和价值。要求在放入背包的物品重量不超过背包容量上限的条件下，获得最大的价值。

以上是背包问题的基本概念，根据拿取物品的规则不同（每个物品只能拿一个，或可以拿多个等）背包问题又可以细分为多个类别。此处只关注基础的两种背包问题，即01背包和完全背包。

如上图所示，根据物品数量，能拿几个，物品是否分组三个条件扩展出五类背包问题。

此处只关注01背包和完全背包。

01背包：每个物品只能拿一个

完全背包：每个物品能拿若干个

基础实现

完全背包问题的基础描述如下：

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

完全背包和01背包的唯一区别就在于每个物品可以被使用多次。而一维的01背包问题有一个限制条件，就是对背包大小j的遍历需要倒序遍历，否则会出现一个物品被拿多次的情况。如果放开这个限制，正好就是完全背包的需求。因此，所有的递推关系，初始化条件都和01背包完全一致，只需要把遍历顺序改成正序即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int getCompletePack(int[] weight, int[] value, int bagWeight) {
    int[] dp = new int[bagWeight + 1];
    for (int i = 0; i < weight.length; i++) { // 遍历物品
        for (int j = weight[i]; j <= bagWeight; j++) { // 遍历背包容量
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    return dp[bagWeight];
}
//先遍历背包，再遍历物品
public int getCompletePack2(int[] weight, int[] value, int bagWeight) {
    int[] dp = new int[bagWeight + 1];
    for (int i = 1; i <= bagWeight; i++) { // 遍历背包容量
        for (int j = 0; j < weight.length; j++) { // 遍历物品
            if (i - weight[j] >= 0) {
                dp[i] = Math.max(dp[i], dp[i - weight[j]] + value[j]);
            }
        }
    }
    return dp[bagWeight];
}

实现细节

先说一下为什么只改一下遍历顺序就行，这里其实隐含了一点贪心的思路，对于当前这个物品，如果一个小容量j下面可以拿一个，之后容量加大到j+k后，如果发现还能再拿一个当前物品，那就再拿一个。这里就是应拿尽拿的贪心思路。

再说一下遍历的内外层顺序，如上面的代码展示，这里先遍历物品还是先遍历背包大小都是可以的。

但是要注意，当题目要求变换时，内外层的顺序就有讲究了。在下面进阶情况中说明。

进阶情况

完全背包的变体主要有以下几类：

  • 不要求最大值，改为判断能否凑出目标值
  • 求能凑出目标值中用物品最少的一种
  • 求所有能凑出目标值的组合数量
  • 求所有能凑出目标值的排列数量
    lc322 零钱兑换

这题就是求凑出目标值的最少物品个数，dp[j]表示凑出和为j的最少硬币个数。则dp[j] = dp[j-coins[i] +1(凑出j-第i个硬币面值的最小个数再加上这一个) 又由于要取最小，那这里应该试试所有可用的硬币面值，取最小的。

dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

lc518零钱兑换II

这题就是求凑出目标值的所有组合个数。dp[j] 表示凑出j的组合个数，则dp[j]应该等于所有j-coins[i]能凑出的个数相加。

因此dp[j] += dp[j - coins[i]]

由于求的是组合数量，所以顺序是无所谓的，即 1 1 2 和 1 2 1 是一样的。如何控制呢？内外层的顺序来控制。

如果外层是物品（此处是硬币）内层是容量，则对于每个硬币，在每个容量下考虑这一次，因此每个硬币其实只出现一次，是组合数。

如果外层是容量，内层是物品，则每个容量下，每个物品都要出现一次，因此变成了排列数。

lc377. 组合总和 Ⅳ

正是要求排列数的完全背包问题

总结：完全背包变体，求能组成目标值的组合个数，应该物品在外，容量在内。求能组成目标值的排列个数，则应该容量在外，物品在内！！！

背包问题总结

递推公式

问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); ，对应题目如下：

动态规划：416.分割等和子集(opens new window)

动态规划：1049.最后一块石头的重量 II(opens new window)

**问装满背包有几种方法：dp[j] += dp[j - nums[i]]**，对应题目如下：

动态规划：494.目标和(opens new window)

动态规划：518. 零钱兑换 II(opens new window)

动态规划：377.组合总和Ⅳ(opens new window)

动态规划：70. 爬楼梯进阶版（完全背包）(opens new window)

**问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);**，对应题目如下：

动态规划：474.一和零(opens new window)

**问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);**，对应题目如下：

动态规划：322.零钱兑换(opens new window)

动态规划：279.完全平方数

遍历顺序

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

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

相关题目如下：

求组合数：动态规划：518.零钱兑换II(opens new window)

求排列数：动态规划：377. 组合总和 Ⅳ (opens new window)、动态规划：70. 爬楼梯进阶版（完全背包）(opens new window)

如果求最小数，那么两层for循环的先后顺序就无所谓了，相关题目如下：

求最小数：动态规划：322. 零钱兑换 (opens new window)、动态规划：279.完全平方数

参考资料

https://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#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

https://programmercarl.com/%E8%83%8C%E5%8C%85%E6%80%BB%E7%BB%93%E7%AF%87.html

算法
#算法
完全背包问题
http://www.bake-data.com/2024/04/01/完全背包问题/
Author
shuchen
Posted on
April 1, 2024
Licensed under