0_1背包问题的多种解法

1、0_1背包问题的多种解法一.问题描述0/1背包问题：现有n种物品，对l=i V二n ,已知第i种物品的重量为正整数Wi,价值为正整数Vi,背包能承受的最大载重量为正整数W ,现要求找出这n种物品的个子集，使得子集中物品的总重量不超过W且总价值尽量大。（注意：这里对每种物品或者全取或者一点都不取,不允许只取一部分）二算法分析根据问题描述,可以将其转化为如下的约束条件和目标函数：冷兀e 0,1） （1 /）ftmax匕兀 /=!于是，问题就归结为寻找一个满足约束条件（1）,并使目标函数式（2 ）达至IJ最大的解向量X =（“/2，召,.,兀）。首先说明一下0-1背包问题拥有最优解。假设（画,勺勺，

2、如）是所给的问题的一个最优解,则（勺，%3，&）是下n面问题的一个最优解：SU，A； V_U，V，max Q內。如果不是的话，设x.e 0,1）（2 /n）1=2（儿，儿，,儿）是这个问题的一个最优解,则/且W內+ X函x S W。因此，彩+vr.yr. 讪+为片兀=为气这说明j-2J-2i-2（-1（州，2*3, 儿）是所给的0-1背包问题比（州宀內占）更优的解,从而与假设矛盾。穷举法：用穷举法解决0-1背包问题，需要考虑给定n个物品集合的所有子集，找 出所有可能的子集（总重量不超过背包重量的子集）,计算每个子集的总重 量,然后在他们中找到价值最大的子集。由于程序过于简单”在这里就不再给 岀

3、，用实例说明求解过程。下面给出了 4个物品和一个容量为10的背包，下 图就是用穷举法求解0-1背包问题的过程。（a）四个物品和一个容量为10的背包序号子隼总重量总价值序号子隼总重量总价值1空集0092,375221742102,48373312113,49654440121,2,314个可行5525131,2,415个可行61,210541413,416个可行71,311个可行1523412个可行81,412个可行16123,419个可行(b )用回溯法求解0-1背包问题的过程递归法：在利用递归法解决0-1背包问题时,我们可以先从第n个物品看起。每次 的递归调用都会判断两种情况：(1)背包可以

4、放下第n个物品，则xn二1,并继续递归调用物品重量为W-wn,物品数目为n-1的递归函数,并返回此递归函数值与vn 的和作为背包问题的最优解；(2 )背包放不下第n个物品，则刈n二0 ,并继续递归调用背包容量为W ,物品数目为n-1的递归函数，并返回此递归函数值最为背包问 题的最优解。递归调用的终结条件是背包的容量为0或物品的数量为0.此时就得到了 0-1背包问题的最优解。用递归法解0-1背包问题可以归结为下函数：KnapSackn-jri)没有选择物品nKnapSacktiijn)=KnapSackn -1, w-vv/?)+v/i 选择了物品 n第个式子表示选择物品n后得至I价值KnapS

5、ackn -1, m-昭川)+皿比 不选择物品n情况下得到的价值KnapSack(n-jn)小,所以最终还是不选择 物品第二个式子刚好相反,选择物品n后的价值KnapSackn-+曲不小于不选择物品n情况下得到了价值 KnapSackn-jn),所以最终选择物品n。在递归调用的过程中可以顺便求出所选择的物品。下面是标记物品被选情况的数组xn求解的具体函数表示：0KnapSack(n.m) = KnapSack(n - l,m)xn = I KnapSack(njn) = KnapSackn -+ vn在函数中，递归调用的主体函数为KnapSack , m表示背包的容量，n表示 物品的数量，刈n

6、表示是否选择了第n个物品(1选,0不选)。每个物 品的重量和价值信息分别存放在数组wn和vn中。具体的代码见递归 法文件夹。贪心法：0-1背包问题与背包问题类似，所不同的是在选择物品/(l/n)装入背包 时，可以选择一部分，而不一定要全部装入背包。这两类问题都具有最优子结 构性质，相当相似。但是背包问题可以用贪心法求解，而0-1背包问题却不能 用贪心法求解。贪心法之所以得不到最优解，是由于物品不允许分割,因此， 无法保证最终能将背包装满,部分闲置的背包容量使背包单位重量的价值降低 了。事实上,在考虑0-1背包问题时,应比较选择物品和不选择物品所导致的 方案，然后做出最优解。由此导出了许多相互重

7、耆的子问题，所以，0-1背包 问题可以用动态规划法得到最优解。在这里就不再用贪心法解0-1背包问题 了。动态规划法分析:0-1背包问题可以看作是寻找一个序列(心心召，兀)，对任一个变量x,的判断是决定旺二1还是斥二0.在判断完之后，已经确定了(召,尤2尤3兀_|),在判断耳时，会有两种情况：(1)背包容量不足以装入物品i ,则x=o,背包的价值不增加；(2 )背包的容量可以装下物品i ,则叮1 ,背包的价值增加V,.。这两种情况下背包的总价值的最大者应该是对X,判断后的价值。令C(M)表示在前1(1/0个物品中能够装入容量为j(lj w.式(1 )说明：把前面i个物品装入容量为0的背包和把0个

8、物品装入容量为j的背包，得到的价值均为0式(2 )第一个式子说明：如果第i个物品的 重量大于背包的容量,则装入第i个物品得到的最大价值和装入第i-1个物品 得到的最大价值是相同的,即物品i不能装入背包中；第二个式子说明：如果 奚i个物品的重量小于背包的容量，则会有两种情况:(1)如果把第i个物 品装入背包，则背包中物品的价值就等于把前i-1个物品装入容量为厂州的 背包中的价值加上第i个物品的价值气；(2)如果第i个物品没有装入背包, 则背包中物品的价值就是等于把前i-1个物品装入容量为j的背包中所取得的 价值。显然，取二者中价值较大者作为把前i个物品装入容量为j的背包中的 最优解。我们可以一步

9、一步的解出我们所需要的解。第一步，只装入第一个物品，确 定在各种情况下背包能得到的最大价值;第二步,只装入前两个物品，确定在 各种情况下的背包能够得到的最大价值；次类推，到了第n步就得到我们 所需要的最优解了。最后,C(,W)便是在容量为W的背包中装入n个物品 时取得的最大价值。为了确定装入背包的具体物品，从C(”W)的值向前寻 找，如果C(n,w) C(-l,w),说明第n个物品被装入了背包中，前n-1个物 品被装入容量为W-叫的背包中；否则，第n个物品没有装入背包中，前n-1个物品被装入容量为W的背包中。依此类推,直到确定第一个物品是否被装入背包为止。由此，我们可以得到如下的函数：roc（

10、/,j）=c（/-i,7）X- = 根据动态规划函数，用一个+ l）x（W + l）的二维数组c存放中间变量,c川刀表示把前i个物品装入容量为j的背包中获得的最大价值。设物品的重量存放在数组wn中”价值存放在数组vn中,背包的容量为W ,数组5卄1叩+ 1存放迭代的结果，数组xn存放装入背包的物品，动 态规划解0-1背包问题的源代码在文件夹动态规划法中。回溯法分析：用回溯法解0_1背包问题时，会用到状态空间树。在搜索状态空间树时，只要其左儿子结点是一个可行结点,搜索就进入其左子树。当右子树有可能包 含最优解时才进入右子树搜索,否则将右子树剪去。设r是当前剩余物品价值 总和；卬是当前价值；bes

11、tp是当前最优价值。当cp+rbestp时，可剪去 右子树。计算右子树中解的上界可以用的方法是将剩余物品依其单位重量价值 排序,然后依次装入物品,直至装不下时,再装入该物品的一部分而装满背 包。由此得到的价值是右子树中解的上界,用此值来剪枝。为了便于计算上界，可先将物品依其单位重量价值从大到小排序,此后只 要顺序考察各物品即可。在实现时，由MaxBoundary函数计算当前结点处 的上界。它是类Knap的私有成员。Knap的其他成员记录了解空间树种的节 点信息,以减少函数参数的传递以及递归调用时所需要的栈空间。在解空间树 的当前扩展结点处,仅当要进入右子树时才计算上界函数MaxBoundary

12、 ,以 判断是否可以将右子树减去。进入左子树时不需要计算上界,因为其上界与父 结点的上界相同。在调用函数Knapsack之前，需要先将各物品依其单位重量价值从达到小 排序。为此目的，我们定义了类Objiect。其中，运算符与通常的定义相 反,其目的是为了方便调用已有的排序算法。在通常情况下,排序算法将待排 序元素从小到大排序。在搜索状态空间树时，由函数Backtrack控制。在函数中是利用递归调用 的方法实现了空间树的搜索。具体的代码见回溯法文件夹。限界分支法：在解0-1背包问题的优先队列式界限分支法中,活结点优先队列中结点元 素N的优先级由该结点的上界函数MaxBoundary计算出的值up

13、rofit给 出。该上界函数在0-1背包问题的回溯法总已经说明过了。子集树中以结点 N为根的子树中任一个结点的价值不超过N.profit.因此我们用一个最大堆来 实现活结点优先队列。堆中元素类型为HeapNode具私有成员有 uprofit,profit,weightjevel,和 pt。对于任意一个活结点 N , N.weight 是活 结点N所相应的重量;N.profit是N所相应的价值；N.uprofit是结点N的 价值上界,最大堆以这个值作为优先级。子集空间树中结点类型为bbnode。在分支限界法中用到的类Knap与0-1背包问题的回溯法中用到的类 Knap很相似。他们的区别是新的类中

14、没有了成员变量bestp ,而增加了新的 成员bestx。Bestxi J当且仅当最优解含有物品i。在类Knap中有四个函数：(1)上界函数MaxBoundary。计算节点所对应价值的上界；(2 )函数AddLiveNodeO是将一个新的活结点插入到子集树?口优先队列 中；(3 )函数MaxKnapsack()实施对子集树的优先队列式分支界限搜索。其 中假定物品依其单位价值从大到小已经排好序。相应的排序过程会 在算法的预处理部分完成。算法中E是当前扩展结点;cw是该结点 的重量；cp是该结点的价值;up是价值上界。算法的while循环 不断扩展结点,直到子集树的一个叶结点成为扩展结点为止。此时

15、 优先队列中所有活结点的价值上界均不超过该叶结点的价值。因此 该叶结点相应的解为问题的最优解。在while循环内部,算法首先检查当前扩展结点的左儿子结点的可 行性。如果该左儿子结点是可行结点,则将它加入到子集树和j召吉 点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当 右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。(4 )函数KnapsackO完成对输入数据的处理。其主要任务是将各物品依 其单位重量价值从达到小排好序。然后调用函数MaxKnapsackO完 成对子集树的优先队列式分支限界搜索。具体的实现代码在文件夹分支限界法中。三.时空效率分析穷举法：对于一个有n个元素的

16、集合，其子集数量为2,所以，不论生成子集的算 法效率有多高,穷举法都会导致一个0(2)的算法。-14递归法：在递归法的算法体中有一个if判断中出现了两次递归调用比较大小所以它们 之间的递归关系式可以大体表示为：T(n) = 2T(n-) + C ,其中八“)表示递 归法的时间复杂度,C是常数。求解递归方程可以知道“)的量级为 0(2)。所以递归法解0-1背包问题的时间复杂度为0(2)。递归法是耗费 空间最多的算法,每次递归调用都需要压栈,导致栈的使用很频繁。动态规划法：由于函数Knapsack中有一个两重for循环，所以时间复杂度为0(n+l)x(m+l).空间复复杂度也是 0(n+l)x(m

17、+l)，即 0 ( nm ).回溯法：由于计算上界的函数MaxBoundary需要0(n)时间，在最坏情况下有 0(2)个右儿子结点需要计算上界，所以解0-1背包问题的回溯法算法 BackTrack所需要的计算时间为0(”2“).限界分支法：在使用限界分治法时,就是使用更好的限界剪枝函数使彳專不必要的解被剔 除，但是在最坏情况下的解仍然是和回溯法是相同的。本算法中也是用到了 计算上界的函数MaxBoundary需要0(n)的时间，而且在最坏情况下有 0(2)个结点需要计算上界,所以在最坏情况下的时间复杂度仍然为 OG2”)。!1!运行结果递归法输岀结果:-1407背包冋题一一递归法IWAW的容

18、量5）和物品个数W :18 7请输入每个物品的重量0）和物品的价值（v）:11 72 84 88 129 13G 410 14背包的最优解为：30最优解条件下选择的背包为：0 1 1 0 0 0 1 背包何题 递归法请输入音包的容量5）和物品个数5）：旷1背包回题一一递归法 请输人音包的容量山）50 10请输入每个物品的重量8 3412 3224 5616 67543235 4521 56和物品个数（）:2和物品的价值19 ?0背包的最优解为：225最优解条件下选择的背包为，10 0 1动态规划法输岀结果:-14000078000078:v)lai* C:UsersAdrr nistvtoDe

19、sltop算法作业模仗200806020053王员0-1苜包可IS动态更辺法 匕152900788888829280 016G16G16o085 61 1G16G160b0785 61 1G16G16000792929282928230301 G281 6291 G291 6湘151600078618 8 81515008816161616If；00882020282028008882R21212128008882021212128008882R21222228请献瞥包的容量5）和物品个数（n；1S 7请一次输入每个物品的重量（u）和价值11 72 8 8 129 136 410 14背包的最

20、优解为，30最优解条件下的选的背包为:0 110 0在此过程中用到的CZW数组数据为, 0t）000请输人普包的容宣（小和物品个数（n； 5R 10请一次输入每个物品的重量）和价值8 34 12 32 24 56 16 67 6 54 9 32 35背包的最优解知225最优解条件下的选S的背包为：1MM11在此过程中用到的c 5 m 数组数扌居为.0 0 0 0 0SJ6fi1846347a34343434fi6” C:UsersAdm nistratorDe$ktopM/fE业棧長莎嬴冷眾隹赢二苜包百动态短辺法旦勺坐魁卩C:UswrsAdm nistvtoDesktop算法作业樓饭20080

21、6020053王员0.1苜包习jg国溯法BacI宁I回07背包冋翹一 一回溯法 请输入背包容Sc：18请输入物品的个数：I-WW人物启的价宿3：7 8 8 12 13 4 14请输入物品的重量5；11 2 4 8 9 6 1Ul15Obestx):液优值为bo3tp：0 110 10 029* C:UsersAdm nistratorDe$ktopM/fflLW2C080602C053 王员0 1 苜邑可IS国溯法E3CL0-1直包冋越回溯法容量 c:50请输入物品的个数：10请输人物启的价S3：34 32 56 67 54 32 4S 56 46 70请输入物品的重量“；8 12 24 16 6 9 35 21 18 1?SffiObestx:販优值为bcotp：110110000018?分枝限界法输岀结果:宀14.14五.分析输岀结果上面测试的是每种算法在两种输入情况下得到的0 J背包问题的解。两种测试i第一组：背包容星:18 ;物品数目：7 ；每个物品为：11 2 4 8 9 6 10;每个物品价值为：7 8 8 12 13 4 140第二组：背包容星:50 ;物品数目：10 ；每