当前位置：首页 > article >正文

背包9讲系列2-完全背包问题

article 2024/11/20 4:18:46

一、前言

又到周末了，这几天可以腾出时间来把背包系列的其他内容好好肝一肝，本次介绍的是完全背包问题，之前的系列内容请查看：
背包9讲系列1-01背包问题

二、完全背包

2.1 问题描述

有n个物品和一个容量为capacity的背包，每种物品有无限多件，他们的体积分别为weights[i](0<=i<n)，价值分别为values[i](0<=i<n)，求将哪些物品装入背包可使价值总和最大？
完全背包问题与01背包问题的区别在于，01背包问题中每种物品最多只能取一次，而完全背包每种物品可以取无限次。

2.2 解体思路

2.2.1 确定状态变量（函数）

最大价值是物品数量i与背包容量j的函数，设dp[i][j]表示从前i件物品中进行选择（每件物品可以选择无限次），放入容量为j的背包所能获得的最大价值

2.2.2 确定状态转移方程（递推关系）

对于第i个物品(第1个物品体积为weights[0]，第i个物品体积为weights[i-1])的选择情况如下：

如果当前背包剩余容量j<weights[i-1]，则无法将该物品装入背包，此时最大价值与从前i-1个物品选择，放入容量为j的背包所能获得的最大价值相同
```
dp[i][j] = dp[i-1][j]
```
如果当前背包剩余容量j>=weights[i-1]，则能放入第i件物品，但是需要判断放入该物品与不放入时哪种情况所能取到的价值最大。

2.1.如果第i件物品不放入背包
```
dp[i][j] = dp[i-1][j]
```
2.2.如果第i件物品放入背包，则背包剩余容量为j-weights[i-1]，在背包9讲系列1-01背包问题中，由于每件物品最多只能取一次，所以剩余的背包容量j-weights[i-1]只能从前i-1件物品中选择并放入（第i件物品已经取过，不能再取），而完全背包的不同之处在于每种物品有无限多件可以选择，也就是说剩余的背包容量j-weights[i-1]可以从前i个物品中选择并放入（第i件物品即使取过也还可以再取），所以最大价值为：第i件物品的价值（values[i-1]）+从前i件物品中选择放入容量为j-weights[i-1]的背包的最大价值（dp[i][j-weights[i-1]]）
```
dp[i][j] = dp[i][j-weights[i-1]] + values[i-1]
```
2.3.所以当j>=weights[i-1]时，我们只需要选择两种情况下的最大值即可
```
dp[i][j] = max(dp[i-1][j], dp[i][j-weights[i-1]] + values[i-1])
```

综上所述，状态转移方程如下：

1.j<weights[i-1]: 
	dp[i][j] = dp[i-1][j]
2.j>=weights[i-1]
	dp[i][j] = max(dp[i-1][j], dp[i][j-weights[i-1]] + values[i-1])

2.2.3 确定边界条件

当背包容量为0时，无法放入任何物品到背包中，总价值为0，即dp[i][0]=0 (0<=i<=n)
当不放入任何物品到背包中时，总价值也为0，即dp[0][j]=0(0<=j<=n)

2.2.4 代码示例

/**
 * @description: 背包问题-背包9讲
 * @author: Tianyi
 * @date: 2023/11/28
 */


public class KnapsackQuestion {
    /**
     * 完全背包
     * 时间复杂度：O(MN)
     * 空间复杂度：O(MN)
     *
     * @param weights  存储n件物品重量的数组，weights[i-1]表示第i件物品的重量(下标从0开始)
     * @param values   存储n件物品价值的数组，values[i-1]表示第i件物品的价值
     * @param capacity 背包的容量
     * @return 从n件物品中进行选择(每件物品可以选择无限次)，放入容量为capacity的背包中所能取得的最大价值
     */
    public int knapsackComplete(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[][] dp = new int[n + 1][capacity + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (j < weights[i - 1]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weights[i - 1]] + values[i - 1]);
                }
            }
        }
        return dp[n][capacity];
    }
}

三、空间优化-滚动数组

由之前的推论可知，dp[i][j]只可能通过dp[i-1][j]或dp[i][j-weights[i-1]]转移而来，设dp[j]为从前i个物品中进行选择（每种物品可以选择无限次），放入容量为j的背包所能获得的最大价值，dp[i][j]和dp[i][j-weights[i-1]]可以分别看作是外层第i次循环所获得的dp[j]和dp[j-weights[i-1]],dp[i-1][j]可看作是外层第i-1(即上一次)循环所获得的dp[j]，状态转移关系如下：

1.j<weights[i-1]: 
	第i次循环得到的dp[j] = 上一次循环得到的dp[j]
2.j>=weights[i-1]
	第i次循环得到的dp[j] = max(上一次循环得到的dp[j], 第i次循环得到的dp[j-weights[i-1]] + values[i-1])

如何在更新dp[j]前保留上一次循环得到的dp[j]和本次循环得到的dp[j-weights[i-1]]？我们可以使用顺序遍历dp数组的方式，令表示容量的内层循环变量j从1增长到capacity，每次循环更新当前的dp[j]，由于j-weights[i-1]肯定要小于j，所以dp[j-weights[i-1]]一定在更新dp[j]之前就已经更新了，而在当前的dp[j]还未被更新之前，dp[j]其实存储的是外层第i-1次循环得到的dp[j]，这样就能满足在更新dp[j]前保留上一次循环得到的dp[j]和本次循环得到的dp[j-weights[i-1]]

for i=1; i <= n; i++
	for j=1; j <= capacity; j++
		if j<weights[i-1]:
			dp[j] = dp[j]
		else:
			dp[j] = Math.max(dp[j], dp[j-weights[i-1]]+values[i-1])

由于j<weights[i-1]时，都是用dp[j]去更新dp[j]，dp[j]实际的值并没有变化，所以可以省略不用写，我们只需要考虑j>=weights[i-1]的情况，即令内层循环变量j从weights[i-1]增长到capacity，示例代码如下：

/**
 * @description: 背包问题-背包9讲
 * @author: Tianyi
 * @date: 2023/11/28
 */


public class KnapsackQuestion {
    /**
     * 完全背包-滚动数组
     * 时间复杂度：O(MN)
     * 空间复杂度：O(M)
     *
     * @param weights  存储n件物品重量的数组，weights[i-1]表示第i件物品的重量(下标从0开始)
     * @param values   存储n件物品价值的数组，values[i-1]表示第i件物品的价值
     * @param capacity 背包的容量
     * @return 从n件物品中进行选择(每件物品可以选择无限次)，放入容量为capacity的背包中所能取得的最大价值
     */
    public int knapsackCompleteWithRollingArray(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[] dp = new int[capacity + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = weights[i-1]; j <= capacity; j++) {
                dp[j] = Math.max(dp[j], dp[j - weights[i - 1]] + values[i - 1]);
            }
        }
        return dp[capacity];
    }
}

四、结尾

本次介绍了完全背包问题的分析思路及代码示例，完全背包与01背包比较类似，需要注意的是，01背包每件物品最多取一次，在用滚动数组进行空间优化时内层循环需要倒序遍历，而完全背包每件物品有无限个，用滚动数组进行空间优化时内层循环需要顺序遍历，如果有不明白的地方欢迎评论区留言探讨。
最近会不定期的更新一系列内容，如果有疑问欢迎评论区留言探讨，感兴趣的小伙伴可以关注我的个人微信公众号，今后会陆续分享各种编程开发技术、业务场景代码设计及优化实践、问题排查解决案例、各类后端技术组件实战及原理、开发工具使用技巧及各类面试题等内容。

天逸技谈