01背包及优化

Leave a comment

March 16, 2017 by oneOokay

01背包:(对于一个物品,取或者不取(取0次和取1次))

  • 一个背包能够给装总重量为W的物品
  • 总共N个物品:
    • 第i个物品的重量为w[i]
    • 第i个物品的价值为v[i]
  • 每个物品可取可不取.(取1次或取0次)

求:背包所能够装的所有物品的最大的总价值为多少.

  • 二维数组
  • 空间优化:一维数组
  • 值的初始化: (背包恰好装满的情况下,背包内所有物品的最大的总价值为多少)
  • 常数的优化:
  • 对于物品进行排序优化
  • 输出路径

假设背包能够装重量为10, 总共5个物品:#0-#4.重量为:{2,2,6,5,4},价值为:{6,3,5,4,6}.开始填这样一个表:

  • header的0-10代表此时背包能够装的总重量W
  • 空的格子里面([n][W])填:当背包能装的总重量为W的时候,考虑装前n个物品(包含n)所能够得到的最大的总价值.
Object NO# Weight Value 0 1 2 3 4 5 6 7 8 9 10
0 2 6
1 2 3
2 6 5
3 5 4
4 4 6

这是一个二维表int[][];顺序从[0][0]开始到[0][10],再从[1][0]到[1][10],以此类推.

  • 第一行对应物品#0: w[0] = 2, v[0] = 6.只考虑第0个物品:
    • W=0和1:物品#0不能放入背包:[0][0]=[0][1]=0.
    • W=2:物品#0刚好可以放入背包:[0][2]=v[0]=6.
    • W=3-10:物品#0一直可以放入背包(此时考虑的物品只有它),所以都填6
  • 第二行对应物品#1: w[1] = 2, v[1] = 3.考虑物品#1和它之前的物品
    • W=0-1:物品#1不能放入背包,所以[1][0]和[1][1]的值为仅考虑物品#0时的最大值:[1][0] = [0][0] = 0, [1][1] = [0][1] = 0.表示W为0-1的时候,物品#0和#1都放不进背包里面.
    • W=2:对于物品#1开始了取或者不取(01背包)的判断.
      • 物品#1不取时,背包依旧能装重W=2. 背包能装的最大价值为:{当背包W=2时,仅考虑物品#1前一个物品(物品#0)时的最大值}:[0][2] = 6.
      • 物品#1取时:背包剩余能装重W=0,此时最大值:v[1] + {当背包W=0的时候,仅考虑物品#1前一个物品(物品#0)时的最大价值:[0][0]}:v[1] + [0][0] = 3 + 0 = 3.
      • 取较大值:max: {6,3}: 所以[1][2]填入6.
      • 代表在背包W=2的时候,考虑物品#1和#0,把#0放入背包能够使得价值最大为6.
    • W=3:
      • 物品#1不取时,背包依旧能装重W=3.背包能装的最大价值为:{当背包W=3时,仅考虑物品#1前一个物品(物品#0)时的最大值}:[0][3] = 6.
      • 物品#1取时:背包剩余能装的重量为1(3-w[i]),此时最大值为v[1] + {当背包W=1的时候,仅考虑物品#1前一个物品(物品#0)时的最大价值:[0][1]}: v[1] + [0][1] = 3 + 0 = 3.
      • 取较大值:max: {6,3}: 所以[1][3]填入6.
      • 代表在背包W=3的时候,考虑物品#1和#0,把#0放入背包能够使得价值最大为6(虽然此时背包依旧还可以装入weight=1的东西).
    • W=4:
      • 物品#1不取时,背包依旧能装重W=4.背包能装的最大价值为:{当背包W=4时,仅考虑物品#1前一个物品(物品#0)时的最大值}:[0][4] = 6.
      • 物品#1取时,背包剩余能装的重量为2,所以此时最大值为v[2] + {当背包W=2的时候,仅考虑物品#1前一个物品(物品#0)时的最大价值:[0][2]}:v[1] + [0][2] = 3 + 6 = 9.
      • 取较大值:max: {6,9}: 所以[1][4]填入9.
      • 代表背包W=4, 考虑物品#1和#0,物品#1和#0都放入背包能够时的价值最大为9.
    • W=5:
      • 物品#1不取时,背包依旧能装重W=5.背包能装的最大价值为:{当背包W=5时,仅考虑物品#1前一个物品(物品#0)时的最大值}:[0][5] = 6.
      • 物品#1取时,背包剩余能装的重量为3,所以此时最大值为v[2] + {当背包W=3的时候,仅考虑物品#1前一个物品(物品#0)时的最大价值:[0][3]}:v[1] + [0][3] = 3 + 6 = 9.
      • 取较大值:max: {6,9}: 所以[1][5]填入9.
      • 代表背包W=4, 考虑物品#1和#0,物品#1和#0都放入背包能够时的价值最大为9.
    • 同理填入W=6-10
  • 同理填入物品#2和物品#3所对应的行.
  • 第5行(物品#4):w[4] = 4, v[4] = 6
    • W为0-3时,物品#4放不进去,所以[4][0]到[4][3]会等于[3][0]到[3][3]的值
    • W=4:物品#4开始0,1判断:
      • 放入:值为v[4] + [3][0] = 6 + 0 = 6
      • 不放:值为[3][4] = 9
      • 取较大值[4][4] = 9
    • [4][5] = 9
    • W为6:
      • 放入:值为v[4]+[3][2] = 6 + 6 = 12
      • 不放:值为[3][6]=9
      • [4][6]=12.
    • 以此类推填完第5行.
  • 最求的结果应该是[4][10]的值:15
Object  Weight Value 0 1 2 3 4 5 6 7 8 9 10
0 2 6 0 0 6 6 6 6 6 6 6 6 6
1 2 3 0 0 6 6 9 9 9 9 9 9 9
2 6 5 0 0 6 6 9 9 9 9 11 11 14
3 5 4 0 0 6 6 9 9 9 10 11 13 14
4 4 6 0 0 6 6 9 9 12 12 15 15 15

综上:维护一个二维数组:dp[i][j]代表:当背包能够装重的最大重量为j的时候,考虑从0到j的物品是否放入背包时,能够达到的包内物品价值最大值.

dp[i][j]  = 取较大值{当不装入物品i(仅考虑前i-1个物品时候)的最大值:dp[i-1][j],装入物品i的最大值:dp[i-1][j-w[i]] + v[i]}  = max {dp[i-1][j], dp[i-1][j – w[i]]}

for (int i = 0; i < N; i ++)
for (int j = 0; j <= W; j ++)
dp [i][j] = max{dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]}

空间优化:

时间复杂度为:W* N;空间复杂度为W*N.时间复杂度优化不了,但是空间可以优化为一个一维数组.

首先外循环:N:0-(N-1)是不变的,或者从(N-1)-0也是没有什么差别.内循环为对于重量W的循环. 一维数组的话就是每一个物体,都要把dp[i]更新一遍.由于dp[i][j]还依赖于一个较小的列dp[i-1][j-w[i]]:所以内层要从W-0循环.这样保证了dp[j-w[i]]是上一个物体的值.(如果从0-W循环的话,dp[j-w[j]]就已经被更新为当前物体的值了)

for (int i = 0; i < N; i ++) 
for (int j = W; j >= 0; j --)
dp [j] = max{dp[j], dp[j - w[i]] + v[i]}

此时填表也是一样的,就是把它想象成一个一维数组就可以了,填表顺序从每一行的最后一个元素开始填.

值的初始化:

“恰好装满背包” VS “并没有要求必须把背包装满”: 区别这两种问法的实现方法是在初始化的时候有所不同。

  • “恰好装满背包”: 那么在初始化时除了f[0]为0其它f[1..V]均设为-∞,这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。
  • “并没有要求必须把背包装满”:初始化时应该将f[0..V]全部设为0。

为什么呢?可以这样理解:初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满,那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”,其它容量的背包均没有合法的解,属于未定义的状态,它们的值就都应该是-∞了。如果背包并非必须被装满,那么任何容量的背包都有一个合法解“什么都不装”,这个解的价值为0,所以初始时状态的值也就全部为0了。

常数的优化:

内层循环j的下限可以进行优化,目前的下限是0.

第一步优化是:每一层循环i:W的下限应该为w[i].因为在W<w[i]的时候,就只能不取物品#i了,此时的dp[j]就会和上一层循环一样,所以不需要更新(因为物品#i放不进去).一般优化到这里就可以了.

进一步优化:最终其实只需要求dp[W].从最后一层循环(n=N-1时)的dp[W]开始往上一层循环推:

最后一层循环:n=N-1: dp[W]需要上一层的dp[W-w[N-1]]被更新:所以上一层循环n=N-2的时候,W的下限应该为w[N-2]和W-w[N-1]之间的一个.

再继续由第n=N-2层循环:我们要知道n=N-2层循环中的dp[W-w[N-1]],所以需要在n=N-3层循环中:dp[W-w[N-1]-w[N-2]]被更新.

由以上可知:第i层循环的W的下限为W-sum(w: i+1 至 N-1)

同时结合第一步优化中的一个下限为w[i].

那么现在的问题是在W-sum(w: i+1至N-1)和w[i]这两个下限中,我们应该取max还是min呢???

应该取max.我目前想不出来太完善的理论支持,就是因为dp[i]是一个递增的数组…

对物品排序进行优化:

网上还有另外一个优化是对于物品按照w[i]从大到小排序,这样能够使得后续物品循环变少.

输出背包里面装的物品:TODO:

参考:

http://love-oriented.com/pack/Index.html

http://www.jianshu.com/p/8d41d87fcbb7

 

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: