背包问题总结

发表于 | | 阅读次数:

背包问题是经典动态规划思想的应用实例。其基本问题是:在拥有一个固定容量的背包的情况下，如何选择不同体积并且价值不同的物品装入背包中，使得背包中的物品的价值最大。也就是说物品有两个维度的属性：体积和价值，而背包限制了总体积。针对这个问题，衍生出不同的背包问题。

0-1背包问题

背包问题的基本条件：背包容量V和一些物品，物品有体积和价值两个属性。0-1背包的问题限制的条件是每个物品只有一种，要么放入背包，要么不放入，如何才能使得背包获得最大的价值，最终的结果，背包可以不被放满。

动态规划

解决方法是动态规划，动态规划解决问题首先要抽象出一个数字化的状态，然后可以确定状态的初始化状态并且可以写出状态的转移方程。后一个状态的转移计算应该依赖于已经计算出来的前面状态(可能是多个)。为了达到全局最优，前一个状态应该是局部最优的，并且后一个状态的计算依赖于前一个状态计算能够达到最终的全局最优，这被称为问题具有最优子结构。并且每一个局部最优状态不会因为后面的计算而发生改变，这被称为无后效性。简单来说，动态规划的一个最优状态依赖于多个局部最优的结果而得出，这也就是为什么动态规划需要填表的原因。贪婪算法从原则上来说动态规划的一种特例，贪婪算法后一个状态只依赖于最优的前一个状态，而不是多个。

解决思路

我们回来来看0-1背包问题，为了计算出指定背包容量的最优值，我们定义一个状态数组，dp[i][j]=maxValue,我们用行标i表示这次尝试放入下标是i的物品，而列标j代表当前的背包的容量，而值maxValue代表将前i个物品放入背包容量为j的背包中所能获取的最大值。当然这个状态的挑选本身并不容易想，这个状态的值决定了在j容量的前提下前i物品的选择最优值，也就是我们说的局部最优，并且它是确定的，不会因为后面的选择而改变。有了这个状态值的定义，我们就可以类似于数学归纳法一样，首先确定初值，然后层层递进求解。
那么初值是什么呢？初值是不放物品的情况下，即i为0的情况下，不论背包容量j有多大，我们的maxValue始终是0，即dp[0][j]=0,这个就是初值。
有了初值后，我们就可以利用这个初值状态计算dp[1][j],dp[2][j]等等，我们需要推出一个通用的公式来求dp[i][j],这样我们就可以用循环来进行迭代计算。要算dp[i][j],也就是尝试将第i个物品放入容量为j的背包，那么我们有两种选择，将i放入背包后的价值and不放入i的价值，我们只有这两种选择，这是个二分选择问题。如果我们将i放入背包，那么肯定要预留i的位置，那么放入i后的价值是dp[i-1][j-w[i]]+v[i],w[i]，v[i]代表i的重量和价值，其中dp[i-1][j-w[i]]是已经计算好的前i-1个物品放入背包容量减去i重量的最大价值，这个是子最优值。另一方面，如果不放入i物品，前i个物品的价值就取前i-1个物品的最优值，即dp[i-1][j]。最后dp[i][j]取这两者的最大值，也就是这次选择的最优值，即dp[i][j]=max{dp[i-1][j-w[i]]+v[i],dp[i-1][j]}。
这个看着复杂的式子就是我们进行迭代计算的根本，后一个的最优值是基于前一个的最优值计算的，如此层层迭代，最终得到我们的结果。回过头来，我们想想这种动态规划的方法为什么会得到全局最优，而贪婪算法却不能，从过程中来看，我们每层的计算都是基于前一层的最优值，并且在最优值上做了二分选择，这是和贪婪策略完全不同之处。
单纯的理论解释不太容易理解，算法的学习最好的方法就是使用例子进行手工推演，看整个过程中数据是如何变化的，这种方法更容易理解算法运作的过程。
下图是我们使用背包为10，尝试从四个重量和价值不同的物品装入，使背包中的价值最大。除了物品编号为0的行都为0外，其他行都是通过我们上面总结的递归公式得来的。例如物品编号为2，背包容量为4的情况下，背包容量是max{dp[1][4-2]+3,dp[1][4]}=max{9,6}=9，所以在背包容量为4时候，前两个物品放入的最大价值是9。
再看个复杂点的，当物品编号是4，背包容量是9的时候，dp[4][9]=max{dp[3][9-5]+4,dp[3][9]}=max{9+4,11}=13。

其中，灰色的部分，是背包容量小于当前的物品重量的情况，这种情况下，只要将dp[i][j]置为dp[i-1][j],而红色部分表示dp[5][10]回溯的过程，可以根据这个回溯过程，看出选择的过程。
有了整个过程了理解，我们很容易写出整个算法过程

1
2
3
4
5
6
7
8
输入：背包容量C，物品个数num，以及每个物品的重量w[i],价值v[i]
输出：当背包容量为C时候的最大价值
置dp[0][j]为0，j<=C
对于第i个物品，i<=num,做如下循环
	对于容量j从0开始，j<=C,做如下循环
		如果j<w[i],则dp[i][j]=dp[i-1][j]
		否则，dp[i][j]=max{dp[i-1][j],dp[i-1][j-w[i]]+v[i]}
返回dp[num][C]即为当背包容量为C时候的最大值

核心java代码实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
int dpValue[][]=new int[stuffNum+1][packCapacity+1];
for(int i=0;i<=packCapacity;i++)
	dpValue[0][i]=0;//不放任何物品的总价值为0
for(int i=1;i<=stuffNum;i++)
	for(int j=0;j<=packCapacity;j++) {
		//如果当前背包容量小于第j个物品的重量,则价值为上一层的最优价值
		if(j<stuffArray[i].getWeight()) 
			dpValue[i][j]=dpValue[i-1][j];
		else {
			//否则，最大值在不放i物品和放i物品之间的价值抉择
			dpValue[i][j]=Math.max(dpValue[i-1][j], (dpValue[i-1][j-stuffArray[i].getWeight()]+stuffArray[i].getValue()));
		}
	}

空间复杂度优化

如果我们仅仅是想得到最终的最大价值结果，而不用进行回溯的话，从数据依赖上看，我们对dp[i][j]的计算仅仅依赖于dp[i-1][j]和dp[i-1][j-w[i]],也就是在更新下标为j的时候仅仅依赖于小于等于j的值，那么我们完全可以使用一维数组来表示状态，而将更新的过程改为逆序的过程，保证在更新j的时候，小于等于j部分的值不被更改，这样的话整个空间复杂度就降成一维数组，改进后的算法技巧主要在第二个循环，我们注意看算法

1
2
3
4
5
6
7
输入：背包容量C，物品个数num，以及每个物品的重量w[i],价值v[i]
输出：当背包容量为C时候的最大价值
置dp[j]全为0，j<=C
对于第i个物品，i<=num,做如下循环
	对于容量j从C开始，j>=w[i],做如下循环
		dp[j]=max{dp[j],dp[j-w[i]]+v[i]}
返回dp[C]即为当背包容量为C时候的最大值

在j<w[i]的时候，保留原值，相当于dp[i][j]=dp[i-1][j]。

0-1背包要求背包装满

如果要求背包必须装满时候的最大价值，那么初始状态dp[0][j]只有dp[0][0]为0，其他状态为不存在状态，只有依赖于存在状态的价值才是可计算的，其他为不可计算，那么我们的算法改为

1
2
3
4
5
6
7
8
9
输入：背包容量C，物品个数num，以及每个物品的重量w[i],价值v[i]
输出：当背包容量为C时候的最大价值
置dp[0][0]为0，其他dp[0][j]=-1, j<=C
对于第i个物品，i<=num,做如下循环
	对于容量j从0开始，j<=C,做如下循环
		如果j<w[i],则dp[i][j]=dp[i-1][j]
		如果dp[i-1][j-w[i]]==-1,则dp[i][j]=dp[i-1][j]
		否则，dp[i][j]=max{dp[i-1][j],dp[i-1][j-w[i]]+v[i]}
返回dp[num][C]不为-1即为当背包容量为C时候的最大值

以上面的例子来看状态数组的更新过程，最终的回溯必然回到dp[0][0]，并且这个过程同样可以使用滚动数组。

完全背包问题

完全背包问题同样是有N种物品和一个容量为C的背包，和0-1背包不同的是每种物品的个数是无限个。这种情况下，其实我们可以将完全背包问题转换成0-1背包问题，不过这会增大循环的过程，使得算法复杂度升高。我们考虑使用另一种方法。
在上面的空间优化过的0-1背包问题中，我们在第二个循环中，使用了倒序更新的方式，原因是我们在要保证上一层更新dp[j]和dp[j-w[i]]是和dp[i-1][j],dp[i-1][j-w[i]],而当每个物品的个数是无限制的情况下，我们的更新需要依赖于我们当前的更新状态，一个大容量的背包可能同时放入多个当前物品。

1
2
3
4
5
6
7
8
---原来的0-1背包算法---
输入：背包容量C，物品个数num，以及每个物品的重量w[i],价值v[i]
输出：当背包容量为C时候的最大价值
置dp[j]全为0，j<=C
对于第i个物品，i<=num,做如下循环
	对于容量j从C开始，j>=w[i],做如下循环//倒序更新
		dp[j]=max{dp[j],dp[j-w[i]]+v[i]}
返回dp[C]即为当背包容量为C时候的最大值

1
2
3
4
5
6
7
8
---完全背包算法---
输入：背包容量C，物品个数num，以及每个物品的重量w[i],价值v[i]
输出：当背包容量为C时候的最大价值
置dp[j]全为0，j<=C
对于第i个物品，i<=num,做如下循环
	对于容量j从0开始，j<=w[i],做如下循环//正序更新
		dp[j]=max{dp[j],dp[j-w[i]]+v[i]}
返回dp[C]即为当背包容量为C时候的最大值

这相当于什么意思呢，相当于二维数组的时候更新的时候dp[i][j]=max{dp[i-1][j],dp[i][j-w[i]]+v[i]},也就是每次更新的值依赖于前面的值，而不是dp[i-1][j-w[i]]+v[i],也就是可以重复放入一个物品，如果使用二维数组解决上面的例子的完全背包问题，我们会得到这样一个状态数组。可以看到，第一个物品被重复放了5次。

多重背包问题

多重背包问题是介于0-1背包和完全背包问题之间，多重背包的每个物品的数量是有限的，是介于1到无限之间的某个数。当然我们仍然可以使用0-1背包问题来解决，假设我们有N种物品，第i个物品的个数是ki,背包容量是C，那我们的时间复杂度就变成了C*(所有k的和)。
如果想要削减时间复杂度，一种方法是将每个k按二进制切分，比如如果数量是7，我们切分成1,2,4三种物品，然后用0-1背包的问题进行求解，这样，时间复杂度就变成了C*(所有log(k)的和)。这样划分可以的原因在于我们可以用通过二进制换分的组合表示一个这个数范围内的所有数。

二维费用背包问题

背包问题的另一个变种是在背包容量和物品重量上的扩展，比如背包容量有两个维度[V,U],比如分别代表体积和重量，而物品的重量也是两个维度[C,D],其实我们仍然可以用前面的思路，不过现在容量变成了二维，而我们的状态数组也变成了三维dp[i][v][u],代表当前i个物品放入背包体积为v和重量为u的情况下的最大价值。转移方程当然也变成了，如果Ci<v或者Di<u,那么dp[i][v][u]=dp[i-1][v][u],否则，dp[i][v][u]=max{dp[i-1][v][u],dp[i-1][v-Ci][u-Di]+V[i]]。结束，当然，我们仍然可以使用空间优化将数组优化到二维数组。

声明

本文首发表于我的博客,欢迎关注！已委托维权骑士为本站的文章进行维权，转载须注明文章出处，作者保留文章所有权。

坚持原创技术分享，您的支持将鼓励我继续创作！