背包问题(转自背包九讲+对应题目)

时间:2022-07-04 18:43:58

一 、01背包问题

 题目

  有N件物品和一个容量为V的背包。放入第i件物品耗费的空间是Ci,得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。

 思路

  这是最基本的背包问题:每种物品仅有一件,可以选择放或不放。

  定义状态:F[i,v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:F[i,v]=max{F[i-1,v],F[i-1,v-Ci]+Wi}

  这个方程很重要,这里来解释一下:“将前i件物品放入容量为v的背包中”这个子问题,若只考虑第i件物品的策略(放还是不放),就可以转化为一个只和前i-1个物品相关的问题。如果不放,则转化为F[i,v];如果放,则为F[i-1,v-Ci]+Wi.

  伪代码如下:

  F[0,0..V] = 0

  for i = 1 to N

    for v = Ci to V

      F[i,v] = max{F[i-1,v],F[i-1,v-Ci]+Wi}

  空间优化

  将空间复杂度降为O(V),即只用一维数组。首先第一层循环一定是有的,每次计算出F[i,0..V]的所有值。由于i是递增变化的,那么我们用一维数组F[0..V],每次循环时都能使用上一次循环的值,也就是i-1的数组值。接下来有个问题,怎么保证F[v]一定是由上一次的F[v]和F[v-Ci]转化过来呢?

  这要求我们在第二层循环时遵循从V到0的递减顺序计算F[v],这样能保证计算F[v]时,F[v-Ci]保存的是上一次的值,即F[i-1,v-Ci]。可以这么理解,由状态转移方程我们知道,F[i,v]是由F[i-1,v]或F[i-1,v-Ci]转化得到,现在只看第二维,每次计算新的F值时都是从第二维比较小的状态过来的,如v和v-Ci,都是小于等于v的,那么只有让第二层从大到小更新,才保证了F[i,v]是由F[i-1,v]或F[i-1,v-Ci]转化得到;否则就成了F[i,v]由F[i,v-Ci]得到的,这是不符合最初的算式的。

  伪代码:

  F[0,0..V] = 0

  for i = 1 to N

    for v = V to Ci

      F[v] = max{F[v],F[v-Ci]+Wi}

  总结

  这样我们可以抽象出一个处理一件01背包的物品过程。

  ZeroOnePack(F,C,W)

    for v = V to C

      F[v] = max(F[v],F[v-C]+W)

 

  有了上述函数,01背包的伪代码就可以这样写:

  F[0..V] = 0

  for i = 1 to N

    ZeroOnePack(F,Ci,Wi)

  初始化问题

  若问题要求刚好装满背包,初始化时,则除了F[0]=0,F[1..V]均为-inf(非法解)。

  如果不要求装满,则初始化时F[0..V]=0。

 

二、完全背包问题

  题目

  有N种物品和一个容量为V的背包,每种物品都有无限件。放入第i件物品耗费的空间是Ci,得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。

  思路

  这个问题于01背包相似,唯一不同的就是这里的物品有无限件。也就是其取法的策略不再是取或不取两种了,而是取0件、取1件······直至取INT(V/Ci)件等多种。

  但我们仍然可以采用解决01背包的思路来求解这个问题。

  列出转移方程:F[i,v]=max{F[i-1,v-k*Ci]+k*Wi | 0<=k*Ci<=v}

  总复杂度为O( V*N*Σ(V/Ci) ),比较大。

  优化

  一个简单有效的优化:若两件物品i、j满足Ci<=Cj且Wi>=Wj,则可以将物品j去掉,不用考虑。

  转化为01背包问题

  把第i种物品拆分成费用为Ci*2^k、价值为Wi*2^k的若干件物品,其中k取满Ci*2^k<=V的非负整数。这就是二进制的思想,因为不管最优策略选几件,其件数总是能表示成若干的2^k件物品的和。这样就把每种物品拆成INT(log(V/Ci))件物品了。

  O(V*N)的算法

  这个算法采用一维数值,先上伪代码:

  F[0,0..V] = 0

  for i = 1 to N

    for v = Ci to V

      F[v] = max{F[v],F[v-Ci]+Wi}

  这个伪代码与01背包的伪代码只有v的循环次序不同而已。

  为什么这个算法要以这样的次序呢?首先想想为什么01背包的中要按照v递减的次序来循环。让v递减是为了保证第i次循环中的状态F[i,v]是由状态F[i-1,v-Ci]递推而来的。换句话说,这正是为了保证每件物品之选一次,保证在考虑“选入第i件物品”这个策略时,依据的是一个绝无已经选入第i件物品的子结果F[i,v-Ci]。而现在完全背包的特点是每种物品可选无限件,所以在考虑“加选一件第i件物品”这种策略时,正需要一个可能已经选入第i种物品的子结果F[i,v-Ci],因此必须采用递增的顺序循环。

  把上述式子写成二维形式:F[i,v]=max{F[i-1,v],F[i,v-Ci]+wi}

  总结  

  最后抽象出处理一件完全背包类物品的过程伪代码:

  CompletePack(F,C,W)

  for v = C to V

     F[v] = max{F[v],F[v-C]+W}

 

三、多重背包问题

  题目

  有N种物品和一个容量为V的背包。第i种物品最多有Mi件,放入第i件物品耗费的空间是Ci,得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。

  思路

  这题和完全背包很相似。只是每种物品最多能取的个数不同了。

  照猫画虎,写出状态转移方程:

       F[i,v] = max{F[i-1,v-k*Ci]+k*Wi | 0<=k<=Mi}

  复杂度是O(V*ΣMi)

  转化为01背包问题

  仍然考虑二进制的思想,我们考虑把第i种物品换成若干件物品,使得原问题中第i种物品可取的每种策略——取0……Mi件——均能等价于取若干件代换以后的物品。另外,取超过Mi的策略不能出现。

  方法是:将第i种物品分成若干件01背包中的物品,其中每一件物品有一个系数。这件物品的费用和价值均是原来的费用和价值乘以这个系数。令这些系数分别为1,2,2^2...2^(k-1),Mi-2^k+1,且k是满足Mi-2^k+1>0的最大整数。例如Mi=13,那么k=3,对应系数分别为1,2,4,6。

  分成的这几件物品的系数和为Mi,表明不可能取多于Mi件的第i种物品。另外这种方法也能保证对于0...Mi间的每一个整数,均可以用若干个系数的和表示。这样就把第i种物品分成了logMi种物品,将复杂度降到了O(V*ΣlogMi)。

  总结

  下面给出O(logM)时间处理一件多重背包中物品的过程:

  MultiplePack(F,C,W,M)

    if C*M >= V

      CompletePack(F,C,W)

      return;

    k = 1

    while k < M

      ZeroOnePack(k*C,k*W)

      M = M - k

      k = 2*k

    ZeroOnePack(M*C,M*W)

  可行性问题O(V*N)的算法

  当问题是“每种有若干件物品能否填满给定容量的背包”,只需考虑填满背包的可行性,不需要考虑每件物品的价值时,多重背包问题同样有复杂度O(V*N)的算法。

  下面介绍一种方法:设F[i,j]表示“用了前i种物品填满容量为j的背包后,最多还剩下几个第i种物品可用”,如果F[i,j]=-1则说明这种状态不可行,若可行应,满足0<=F[i,j]<=Mi。

  递推求F[i,j]的伪代码如下:

  F[0,1...V] = -1

  F[0,0] = 0

  for i = 1 to N

    for j = 0 to V

      if F[i-1,j] >= 0

        F[i,j] = Mi

      else

        F[i,j] = -1

    for j = 0 to V-Ci

      if F[i,j] > 0

        F[i,j+Ci] = max{F[i,j+Ci,F[i,j]-1}  

  最终F[N,0...V]便是多重背包可行性问题的答案。

 

四、混合三种背包问题

  若有的物品只能取一次,有的物品可取无限次,有的物品可取Mi次。该怎么求解呢?

  最清晰的做法时使用上述定义的三个过程:

  for i = 1 to N

    if 第i件物品属于01背包

      ZeroOnePack(F,Ci,Wi)

    else if 第i件物品属于完全背包

      CompletePack(F,Ci,Wi)

    else if 第i件物品属于多重背包

      MultiplePack(F,Ci,Wi,Mi)