动态规划之完全背包问题解题方法

完全背包是经过01背包演变而来的，区别就是完全背包问题中物品是有无限个的，也就是说一个物品可以放入背包多次。同样的LeetCode上也没有纯完全背包的问题，都是完全背包应用方面的题目，也就是需要将其转化为完全背包问题。所以，记录一下从代码随想录-完全背包理论基础学习到纯完全背包问题的解题方法，补充一下纯完全背包的二维dp数组的解法，具体应用题需要靠自己来将其转化成完全背包，dp数组状态转移方程、初始化、遍历顺序可能会和纯完全背包问题有一些不同，需要具体问题具体分析。

概念

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

例子

背包最大重量为4，每个物品有无限个，物品的重量和价值如下：

	重量	价值
物品0	1	15
物品1	3	20
物品2	4	30

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

解题方法

动规五部曲

1.确定dp数组以及下标的含义

使用二维数组，dp[i][j]数组表示从前i个物品中任意取，放进容量为j的背包中所得到的物品的最大价值。

2.递推公式(状态转移方程式)

对于每个物品来说有两种选择，不选取或选取。所以dp[i][j]可以从这两类选择中推导出：

• 不选取物品i：

  由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，即dp[i][j] = dp[i - 1][j]。

• 选取物品i：

  **由dp[i][j - weight[i]]推出，注意这里和01背包的区别，因为可以重复放物品i，所以是dp[i][j - weight[i]]**，表示背包容量为j - weight[i]的时候任取物品i的最大价值，那么dp[i][j - weight[i]] + value[i]（物品i的价值） ，就是背包放物品i得到的最大价值，即dp[i][j] = dp[i][j - weight[i]] + value[i]。

所以，递推公式为：

• 如果物品i的重量大于背包容量j时，背包放不下，就不能选择物品i，dp[i][j] = dp[i - 1][j]；
• 如果物品i的重量小于等于背包容量j时，dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])。

3.dp数组的初始化

关于初始化，一定要和dp数组的定义一致。

两种初始化情况：

• 背包容量j为0，不管选择哪些物品，所得到的物品最大价值一定为0，所以dp[i][0] = 0；
• 物品数量为0时，不论背包容量多大，所得到的物品最大价值一定为0，所以dp[0][j] = 0。

dp[i][j](物品\背包)	0	1	2	3	4
无物品	0	0	0	0	0
物品0	0
物品1	0
物品2	0

4.dp数组的遍历顺序

有两个遍历的维度：物品和背包，那么问题来了，先遍历物品还是先遍历背包重量呢？

其实都可以，因为递推公式为dp[i][j] = dp[i - 1][j]和dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])这两种情况，不论哪种，dp[i - 1][j]和dp[i][j - weight[i]]都在dp[i][j]的左上角方向，而两种遍历顺序都能够获取到dp[i][j]左上角方向的值，先遍历物品会更好理解。

• 先遍历物品再遍历背包，代码如下

// m为物品的个数，n为背包的容量
int m = weight.length, n = bagWeight;
// m + 1是考虑没有任何物品的情况，n + 1是考虑背包容量为0的情况
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) { // 遍历物品
    for (int j = 0; j <= n; j++) { // 遍历背包
        if (j < weight[i - 1]) {
            dp[i][j] = dp[i - 1][j];
        } else {
            // 注意这里跟01背包只有下面一个下标不同，那就是“放i”这个选择，因为是可以重复放的，所以是dp[i]
            dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i - 1]] + value[i - 1]);
        }
    }
}

• 先遍历背包再遍历物品，代码如下

// m为物品的个数，n为背包的容量
int m = weight.length, n = bagWeight;
// m + 1是考虑没有任何物品的情况，n + 1是考虑背包容量为0的情况
int[][] dp = new int[m + 1][n + 1];
for (int j = 0; j <= n; j++) { // 遍历背包
    for (int i = 1; i <= m; i++) { // 遍历物品
        if (j < weight[i - 1]) {
            dp[i][j] = dp[i - 1][j];
        } else {
            // 注意这里跟01背包只有下面一个下标不同，那就是“放i”这个选择，因为是可以重复放的，所以是dp[i]
            dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i - 1]] + value[i - 1]);
        }
    }
}

5.打印dp数组

dp数组对应值如下：

dp[i][j](物品\背包)	0	1	2	3	4
无物品	0	0	0	0	0
物品0(重量1，价值15)	0	15	30	45	60
物品1(重量3，价值20)	0	15	30	45	60
物品2(重量4，价值30)	0	15	30	45	60

完整代码

// m为物品的个数，n为背包的容量
int m = weight.length, n = bagWeight;
// m + 1是考虑没有任何物品的情况，n + 1是考虑背包容量为0的情况
int[][] dp = new int[m + 1][n + 1];
// dp[i][0]和dp[0][j]情况的初始化省略，因为dp数组的默认值就是0
for (int i = 1; i <= m; i++) { // 遍历物品
    for (int j = 0; j <= n; j++) { // 遍历背包
        if (j < weight[i - 1]) {
            dp[i][j] = dp[i - 1][j];
        } else {
            // 注意这里跟01背包只有下面一个下标不同，那就是“放i”这个选择，因为是可以重复放的，所以是dp[i]
            dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i - 1]] + value[i - 1]);
        }
    }
}
return dp[m][n];

优化为一维dp数组

由于递推公式中dp[i][j]用到了dp[i - 1][j]和dp[i][j - weight[i]]即上一层和左边的数据，所以可以将dp[i][j]优化为dp[j]。

dp数组以及下标的含义

这里dp[j]数组的表示容量为j的背包中所得到的物品的最大价值。

递推公式(状态转移方程式)

递推公式变为dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])。

dp数组的初始化

dp[0] = 0即可

dp数组的遍历顺序

01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次；而完全背包的物品是可以添加多次的，所以要从小到大去遍历。

// m为物品的个数，n为背包的容量
int m = weight.length, n = bagWeight;
int[] dp = new int[n + 1];
for (int i = 1; i <= m; i++) {
    // 注意这里遍历背包顺序又变成了正序，和01背包不同，很重要
    for (int j = weight[i - 1]; j <= n; j++) {
        dp[j] = Math.max(dp[j], dp[j - weight[i - 1]] + value[i - 1]);
    }
}

这里完全背包一维dp数组可以交换遍历顺序吗？

和01背包不同，这里是可以的！因为dp[j]是用到其左边的数据dp[j - weight[i]]的，而先遍历背包再遍历物品也是满足的。

打印dp数组

略

一维数组完整代码

// m为物品的个数，n为背包的容量
int m = weight.length, n = bagWeight;
int[] dp = new int[n + 1];
for (int i = 1; i <= m; i++) {
    // 注意这里遍历背包顺序又变成了正序，和01背包不同，很重要
    for (int j = weight[i - 1]; j <= n; j++) {
        dp[j] = Math.max(dp[j], dp[j - weight[i - 1]] + value[i - 1]);
    }
}
return dp[n];