Question

0-1背包问题入门详解

Answer 1

网上好多关于背包问题的解释，自己也看了，感觉解释的不容易通俗易懂，所以自己来写一个非常容易懂得。

0-1背包问题说的是，给定背包容量W，一系列物品{weiht,value}，每个物品只能取一件，获取最大值。

采用动态规划求解，动态规划的一般规律都是，

在什么什么前i个状态下的最大值或者最小值的前提下，然后再把i的状态的值求出来。

这里我们定义一个函数，表示状态。

m(1,2,3,4..i)(w)表示有1号,2号,3号,4号....i号物品，背包容量为w的时能够取得的最大值。举例说明，

假设1，2,3,4,5号物品，它们的重量分别是2,2,6,5,4，用weight(i)表示，它们的价值分别是6,3,5,4,6用value(i)表示

m(1)(1)表只有1号物品，背包容量为1的时候，最大值。显然，

m(1)(1) = 0，因为背包容量小于2，所以最大值为0。

m(1)(2) = 6, 此时背包容量等于2，装下1号物品，最大值为6，接下来

m(1)(3) = 6,m(1)(4) = 6，...m(1)(..) = 6,因为只有一件物品，最大为6。

m(1,2)(1),m(1,2)(2),m(1,2)(3)表示有物品1号，2号，背包容量分别为1,2,3的时候最大值。

最大值和物品的数量相关，也和背包容量相关。

这里必须强调一下，m(1,2,3,...i)(w) 表示有1,2,3,4....i，这么多物品可选，未必全部装进去的情况下(受限于w)的最大值。

接下来讨论在1,2,3.....i物品的最大值。对于第i件物品，背包容量为W，有两种情况，

1）不把第i件物品装进背包，那么此时，只有1,2,3,4,,,,i-1件物品，背包的最大值是m(1,2,3,4,5....i-1)(W)。此时，不管W多么大，即使和宇宙一样大，背包里的价值之和1,2,3,4,5..i-1这些物品相关。

2）把第i件物品装进去。既然把i件物品装进背包，那么1,2,3,4.....i-1物品只能占用 W-weight(i) 这么多重量了。这个时候，

之前的1,2,3,4......i-1物品在背包容量为（W-weight(i)）下的最大值为m(1,2,3.......i-1)[ W - weight(i) ]。

此时背包的最大值就是 第i件物品的价值value(i)加上

前1,2,3,4....i-1件物品在背包容量为（W-weight(i) 下的最大值m(1,2,3.......i-1)[ W - weight(i) ]

m（1,2,3,4.......i-1,i)(W)= m(1,2,3.......i-1)[ W - weight(i) ] +   value(i) ;

然后我们比较一下，情况1）2）的最大值就可以了 即

m(1,2,3,4....i-1,i)(W) = max[  m(1,2,3.......i-1)[ W - weight(i) ] +   value(i) , m(1,2,3,4,5....i-1)(W) ]。 

这里有人会说，前1,2,3,4.....i-1件物品在W-weight或者W的容量下怎么求啊。

这里就说到动态规划的点上。动态规划有点数学归纳法的感觉，不过是从后向前推到，要求解i，先求解i-1,；要求解i-1，先求解i-2，这样一步一步到2,1。因此需要给定初始状态。我们一直用1,2,3,4.....i-1表示前i-1件物品，太麻烦，直接用i-1表示好了。

m(1,2,3,4....i-1)(w) ====(书写方便)>m(i-1)(w)，这样上面的状态转移方程就出来。

m(i)(W) = max( m(i-1)(W- weight(i))+value(i), m(i-1)(w) )

这样，状态的转移方程就出来。这里不得不说下，网上的其他教程这一点上说的不够仔细，上来就搞一个

f[i-1][j] = max(f[i-1][j-w(i)]+value[i],f[i-1][j])。谁看的懂啊。

这里我们针对上面的数值给出具体的求解过程。首先给出物品的函数值。

weight(1) = 2,value(1) = 6,

weight(2) = 2,value(2) = 3,

weight(3) = 6,value(3) = 5,

weight(4) = 5,value(4) = 4,

weight(5) = 4,value(5) = 6,

那么最大值函数

m(1)(1) = 0；物品重量为2.

m(1)(2) = 6, 物品恰好放入背包。

m(1)(3) = 6，m(1)(4) = 6...，只有1号物品，最大值只能为6。现在考虑有第2件物品的情况，现在有两件物品，m函数表示为

m(1,2)(w)。

根据之前所说 1），如果不把2号物品放入，那问题回到只有1号物品的情况

那么

m(1)(1) = 0,1号物品放不进，

m(1)(2) = 6, 1号物品放进背包。

m(1)(3) = 6, 1号物品放进容量为3的背包

m(1)(4) = 6, 1号物品放进容量为4的背包。

根据之前所说2），把2号物品放入，此时需要 1号物品在背包容量w减去2号物品的容量weight(2),即 w-2的问题。

m(1)(1 - 2) = 0,显然，此时背包总容量为1，还有减去2号物品的容量2，1-2=-1 ，显然放不进去。

m(1)(2 - 2) = 0,显然，背包的容量减去2号物品的容量后，没有剩余，就是说只能放2号物品，此时背包的最大值

m(1,2)(2)  =  max(m(1,2)(2-2)+value(2),  m(1)(2))= max(0+3,6) = 6。就是说，在有1,2两件物品，背包容量为2的情况下，最大值为6。

继续考虑背包容量为3，第一种情况的已经讨论。现在讨论第二种情况，把2号物品放入背包，就要剩下w-2的容量给1号了。

m(1,2)(w-2)= m(1,2)(3-2)=m(1,2)(1)  = 0, value(2) = 3因此，

m(1,2)(3) = max[ m(1,2)(3-2)+value(2),m(1)(3)] = max(0+3,6) = 6。

继续考虑背包容量为4，同理，第一种情况讨论，只讨论第二种情况，把2号物品放入背包，就要剩下w-2的容量给1号了。

m(1,2)(4-2)=m(1,2)(2)=6,value(2) = 3

m(1,2)(4) = max[ m(1,2)(4-2)+value(2),m(1)(4)]=max[m(1,2)(2)+value(2),m(1)(4)] = max(6+3,6) = 9;

此时m(1,2)(4) = 9;之后，背包容量为5，6,7，。的时候，1,2物品都放进去，最大值不再改变，都是9

m(1,2)(5) = 9，m(1,2)(6) = 9，m(1,2)(7) = 9，m(1,2)(8) = 9

同理，weight(3) = 6,value(3)=5

m(1,2,3)(1) = max[ m(1,2,3)(1-6)+value(3),m(1,2)(1) ] = 0

m(1,2,3)(2) = max[ m(1,2,3)(2-6)+value(3),m(1,2)(2)  ] =6

m(1,2,3)(3) = max[ m(1,2,3)(3-6)+value(3),m(1,2)(3)  ] =6

m(1,2,3)(4) = max[ m(1,2,3)(4-6)+value(3),m(1,2)(4)  ] =9

m(1,2,3)(5) = max[ m(1,2,3)(5-6)+value(3),m(1,2)(5)  ] =9

m(1,2,3)(6) = max[ m(1,2,3)(6-6)+value(3),m(1,2)(6)  ] = 9

m(1,2,3)(7) = max[ m(1,2,3)(7-6)+value(3),m(1,2)(7)  ] = max[m(1,2,3)(1)+5,9] = max[0+5,9]=9

m(1,2,3)(8) = max[ m(1,2,3)(8-6)+value(3),m(1,2)(8)  ] = max[m(1,2,3)(2)+5,9] = max[6+5,9]=11;

剩下的推导都是如此，根据背包容量一步一步的推导即可。