算法设计 - 01背包问题的状态转移方程优化，以及完全背包问题

妖狐艹你老母 2023-09-24 16:53 123阅读 0赞

## 01背包问题的一维状态转移方程的推导 ##

### 前提摘要 ###

前面这篇博客中：

[算法设计 - 01背包问题\_伏城之外的博客-CSDN博客][- 01_-CSDN]

我们已经推导出了01背包问题的二维数组dp状态转移方程公式：

> 假设有N种不同物品，且每种物品只有1个，第 i 个物品的重量表示为w\[i\]，价值表示为p\[i\]，现在有一个背包，其承重是W，现要求该背包装物品能得到的最大价值是多少？

dp\[i\]\[0\] = 0，dp\[0\]\[j\] = 0

*  if w\[i\] <= W ：dp\[i\]\[j\] = Math.max(dp\[i-1\]\[j\], dp\[i-1\]\[j - w\[i\]\] + p\[i\])
 *  else：dp\[i\]\[j\] = dp\[i-1\]\[j\]

二维数组中元素**dp\[i\]\[j\]**的含义是：

物品可选范围为**0~i**，当背包承重固定为 **j**，所能得到的最大价值为dp\[i\]\[j\]。

如果，还不能理解上面状态转移方程，请先看这篇博客：[算法设计 - 01背包问题\_伏城之外的博客-CSDN博客][- 01_-CSDN]

### 一维状态转移方程的推导 ###

前面推导出来的是一个二维状态转移方程，其方程中最关键的一个是：

> dp\[i\]\[j\] = Math.max(dp\[i-1\]\[j\], dp\[i-1\]\[j - w\[i\]\] + p\[i\])

其实这个方程可以这样看：

dp**\[i\]****\[j\]** 要么等于 dp**\[i-1\]****\[j\]**，要么等于dp**\[i-1\]\[j - w\[i\]\]** \+ p\[i\]

如果在二维矩阵中看的话，其实就如下图

![8103a31d70df43cb861b8dcf5637e93f.png][]

可以发现dp\[i\]\[j\]值完全是由它前一行的两个值推导出来的，并且这两个值dp\[i-1\]\[j\] 和 dp\[i-1\]\[j - w\[i\]\] 一定是处于dp\[i\]\[j\] 的 上方以及左上方。

其实，此时，有一个现象，那么就是物品选择和背包承重变化，和dp二维数组重合了，如果我们dp二维数组解耦出来，会得到两个矩阵：

![a4cca77bc0a3435395fa1ee60e111587.png][]

对应到代码来看，左边其实就是遍历二维矩阵的流程（外层遍历物品范围，内层遍历背包承重），右边dp\[i\]\[j\]只是用于缓存结果的。

// 一共N个物品
    // 第i个物品的重量为w[i]，价值为p[i]
    // 背包的承重为W
    
    // 在所有物品最前面添加一个重量0，价值0的虚拟物品，下面是伪代码
    w.addFirst(0)
    p.addFirst(0)
    
    // dp数组的行数对应物品数量，由于新增了一个虚拟物品，因此有N+1个物品
    // dp数组的列数对应背包承重，需要一个承重0的背包，并且最大承重W要包含，因此需要W+1种背包承重
    int[][] dp = new int[N+1][W+1] // 初始化二维矩阵
    
    // 遍历矩阵
    for(int i=0; i<=N; i++) {
    	for(int j=0; j<=W; j++) {
    		if(i==0 || j==0) continue; // 因为dp[i][0]，以及dp[0][j]的结果都为0，没必要更新
    		if(W < w[i]) dp[i][j] = dp[i-1][j]; // 如果要放入背包的第i个物品的重量超过了背包，则不能放入该物品
    		else dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - w[i]] + p[i]) // 如果选择不放入第i个物品，则dp[i-1][j]，如果选择放入第i个物品，则dp[i-1][j - w[i]] + p[i]
    	}
    }

那么，此时，我们再来看，是否有必要搞个二维数组来缓存结构呢？

![8103a31d70df43cb861b8dcf5637e93f.png][]

如果我们将每次得到的结果都存在一行上（即一维数组上），那么会发生什么呢？即如下图所示

![cf30758b23c045399abf50b03b5b9b41.png][]

即如下代码：

// 一共N个物品
    // 第i个物品的重量为w[i]，价值为p[i]
    // 背包的承重为W
    
    // 在所有物品最前面添加一个重量0，价值0的虚拟物品，下面是伪代码
    w.addFirst(0)
    p.addFirst(0)
    
    int[] dp = new int[W+1] // 去除行概念
    
    // 遍历流程不变
    for(int i=0; i<=N; i++) { // 物品从0~i中选择
    	for(int j=0; j<=W; j++) { // 背包承重为j
    		if(i==0 || j==0) continue;
    
            // 上图橙色线如下两行代码：
    		if(j < w[i]) continue; // 相当于dp[j]保持不变
    		dp[j] = Math.max(dp[j], dp[j - w[i]] + p[i])
    	}
    }

即原本应该保存到下一行的newVal，被保存在了本行。那么这么做是否可行呢？

![90688ce72ea04fd9aabdfcc2956d6a2a.png][]

答案是不可行，因为假设现在要求解的 dp\[j + 1\] = Math.max(dp\[j+1\], **dp\[j + 1 - w\[i\]\] + p\[i\]**) 中 **dp\[j + 1 - w\[i\]\] + p\[i\]** 刚好就是上一轮更新过的dp\[j\]的值,那么就和二维方程时的实现产生差异了。

因为，此时d\[j\]已经是newVal了，而按照二维方程时的推导，dp\[j+1\]应该要取值于**变成newVal之前的dp\[j\]**。

因此上面代码实现不可取。

但是，其实只要在一个地方做一个小改动，即可避免上述问题。

那就是，将内层遍历改为从 W 遍历到 0，即反向遍历，此时，我们会首先计算出如下dp\[i\]，并将计算出的newVal更新回dp\[j\]

![af5759e30b804f4482dd87eef7178792.png][]

然后下一个计算的是dp\[j-1\]

![76d1a042c8564012a3a3709ae2968c63.png][]

此时，上一轮更新的dp\[j\]就不会影响到下一轮了。

因此，我们可得一个关键注意点，那就是将01背包问题的二维状态转移方程，升级为一维状态转移方程时，**内层对背包承重的遍历，必须反向遍历**。代码如下：

// 一共N个物品
    // 第i个物品的重量为w[i]，价值为p[i]
    // 背包的承重为W
    
    // 在所有物品最前面添加一个重量0，价值0的虚拟物品，下面是伪代码
    w.addFirst(0)
    p.addFirst(0)
    
    int[] dp = new int[W+1] // 去除行概念
    
    // 遍历流程不变
    for(int i=0; i<=N; i++) { // 物品从0~i中选择
    	for(int j=W; j>=0; j--) { // 背包承重为j，注意，一维方程时，这里要反向遍历
    		if(i==0 || j==0) continue;
    
            // 上图橙色线如下两行代码：
    		if(j < w[i]) continue; // 相当于dp[j]保持不变
    		dp[j] = Math.max(dp[j], dp[j - w[i]] + p[i])
    	}
    }

## 完全背包问题 ##

要想学习完全背包问题的解法，必须先学会01背包问题的一维状态转移方程。

下面是完全背包问题的描述：

> 假设有N种不同物品，**且每种物品有无数个**，第 i 个物品的重量表示为w\[i\]，价值表示为p\[i\]，现在有一个背包，其承重是W，现要求该背包装物品能得到的最大价值是多少？

对比前面关于01背包问题的描述，可以发现，二者的区别仅在于 完全背包问题 种，每种物品可以有多个，而不是只有一个。

这里，我们先说完全背包如何解决？

其实，很简单，就是将01背包问题中，对于背包承重的反向遍历，改为正向遍历即可，代码如下

// 一共N种物品，每种物品有多个
    // 第i种物品的重量为w[i]，价值为p[i]
    // 背包的承重为W
    
    // 在所有物品最前面添加一个重量0，价值0的虚拟物品，下面是伪代码
    w.addFirst(0)
    p.addFirst(0)
    
    int[] dp = new int[W+1] // 去除行概念
    
    // 遍历流程不变
    for(int i=0; i<=N; i++) { // 物品从0~i中选择
    	for(int j=0; j<=W; j++) { // 背包承重为j，区别于01背包，完全背包，这里要求背包承重遍历正向进行
    		if(i==0 || j==0) continue;
    
            // 上图橙色线如下两行代码：
    		if(j < w[i]) continue; // 相当于dp[j]保持不变
    		dp[j] = Math.max(dp[j], dp[j - w[i]] + p[i])
    	}
    }

原理其实前面我们已经说明了，如下图所示

![90688ce72ea04fd9aabdfcc2956d6a2a.png][]

正向遍历时，dp\[j+1\]的值，其实是可能从已经更新为newVal的dp\[j\]种获取的，而已经变成newVal的dp\[j\]其实又是包含多个物品选择的。这样一级一级往前推导，其实就实现了一种物品被选择多次的情况。

[- 01_-CSDN]: https://fcqian.blog.csdn.net/article/details/128307663
[8103a31d70df43cb861b8dcf5637e93f.png]: https://img-blog.csdnimg.cn/8103a31d70df43cb861b8dcf5637e93f.png
[a4cca77bc0a3435395fa1ee60e111587.png]: https://img-blog.csdnimg.cn/a4cca77bc0a3435395fa1ee60e111587.png
[cf30758b23c045399abf50b03b5b9b41.png]: https://img-blog.csdnimg.cn/cf30758b23c045399abf50b03b5b9b41.png
[90688ce72ea04fd9aabdfcc2956d6a2a.png]: https://img-blog.csdnimg.cn/90688ce72ea04fd9aabdfcc2956d6a2a.png
[af5759e30b804f4482dd87eef7178792.png]: https://img-blog.csdnimg.cn/af5759e30b804f4482dd87eef7178792.png
[76d1a042c8564012a3a3709ae2968c63.png]: https://img-blog.csdnimg.cn/76d1a042c8564012a3a3709ae2968c63.png