算法分析与设计实验报告之01背包问题

算法分析与设计实验报告[0/1背包问题]0/1背包问题的不同算法解决方案组员0945532112黄希龙09455321张育强0945532145周麒目录一.问题描述......................................................................................................................................1二.算法分析............................................................................................21.穷举法：................................................................................................................................22.递归法：................................................................................................................................43.贪心法：................................................................................................................................54.动态规划法分析：................................................................................................................65.回溯法分析：........................................................................................................................76.分支限界法：........................................................................................................................9三.时空效率分析..................................................................................101.穷举法：..............................................................................................................................102.递归法：..............................................................................................................................113.动态规划法：......................................................................................................................114.回溯法：..............................................................................................................................115分支限界法：......................................................................................................................11四.运行结果..........................................................................................121.穷举法输出结果：..............................................................................................................122.递归法输出结果：..............................................................................................................133.动态规划法输出结果：......................................................................................................144.回溯法输出结果：..............................................................................................................155.分支限界法输出结果：......................................................................................................16五.分析输出结果..................................................................................17六.总结与反思......................................................................................18一.问题描述0/1背包问题:现有n种物品，对1=i=n，已知第i种物品的重量为正整数Wi，价值为正整数Vi，背包能承受的最大载重量为正整数W，现要求找出这n种物品的一个子集，使得子集中物品的总重量不超过W且总价值尽量大。（注意：这里对每种物品或者全取或者一点都不取，不允许只取一部分）二.算法分析根据问题描述，可以将其转化为如下的约束条件和目标函数：)2(max)1()1}(1,0{11niiiiniiixvnixWxw于是，问题就归结为寻找一个满足约束条件（1），并使目标函数式（2）达到最大的解向量),......,,,(321nxxxxX。首先说明一下0-1背包问题拥有最优解。假设),......,,,(321nxxxx是所给的问题的一个最优解，则),......,,(32nxxx是下面问题的一个最优解：niiiiniiixvnixxwWxw2211max)2}(1,0{。如果不是的话，设),......,,(32nyyy是这个问题的一个最优解，则niniiiiixvyv22，且niiiWywxw211。因此，niiininiiiiixvxvxvyvxv1221111，这说明),........,,,(321nyyyx是所给的0-1背包问题比),........,,,(321nxxxx更优的解，从而与假设矛盾。1.穷举法：用穷举法解决0-1背包问题，需要考虑给定n个物品集合的所有子集，找出所有可能的子集（总重量不超过背包重量的子集），计算每个子集的总重量，然后在他们中找到价值最大的子集。由于程序过于简单，在这里就不再给出，用实例说明求解过程。下面给出了4个物品和一个容量为10的背包，下图就是用穷举法求解0-1背包问题的过程。W1=7V1=12W2=3V2=12W3=4V3=40W4=5V4=2510背包物品1物品2物品3物品4（a）四个物品和一个容量为10的背包序号子集总重量总价值序号子集总重量总价值1空集009{2，3}7522{1}74210{2，4}8373{2}31211{3，4}9654{3}44012{1,2,3}14不可行5{4}52513{1,2,4}15不可行6{1，2}105414{1,3,4}16不可行7{1，3}11不可行15{2,3,4}12不可行8{1，4}12不可行16{1,2,3,4}19不可行穷举法代码如下:#includeiostream.h#includemath.h#includestdlib.h#defineMAX100//限定最多物品/*将n化为二进制形式，结果存放到数组b中*/voidconversion(intn,intb[MAX]){inti;for(i=0;iMAX;i++){b[i]=n%2;n=n/2;if(n==0)break;}}voidmain(){system(title0/1背包问题——穷举法);2.递归法：在利用递归法解决0-1背包问题时，我们可以先从第n个物品看起。每次的递归调用都会判断两种情况：（1）背包可以放下第n个物品，则x[n]=1，并继续递归调用物品重量为W-w[n],物品数目为n-1的递归函数，并返回此递归函数值与v[n]的和作为背包问题的最优解；（2）背包放不下第n个物品，则x[n]=0，并继续递归调用背包容量为W，物品数目为n-1的递归函数，并返回此递归函数值最为背包问题的最优解。递归调用的终结条件是背包的容量为0或物品的数量为0.此时就得到了0-1背包问题的最优解。用递归法解0-1背包问题可以归结为下函数：][])[,1(),1(),(nvnwmnKnapSackmnKnapSackmnKnapSacknn选择了物品没有选择物品第一个式子表示选择物品n后得到价值][])[,1(nvnwmnKnapSack比不选择物品n情况下得到的价值),1(mnKnapSack小，所以最终还是不选择物品n;第二个式子刚好相反，选择物品n后的价值][])[,1(nvnwmnKnapSack不小于不选择物品n情况下得到了价值),1(mnKnapSack，所以最终选择物品n。在递归调用的过程中可以顺便求出所选择的物品。下面是标记物品被选情况的数组x[n]求解的具体函数表示：10][nx][])[,1(),(),1(),(nvnwmnKnapSackmnKnapSackmnKnapSackmnKnapSack在函数中，递归调用的主体函数为KnapSack，m表示背包的容量，n表示物品的数量，x[n]表示是否选择了第n个物品（1—选，0—不选）。每个物品的重量和价值信息分别存放在数组w[n]和v[n]中。代码如下:#includeiostreamusingnamespacestd;intcw=0,bp=0,m,c,i,j,v=0;//cw为当前背包中物品的重量，intprice[1000];//记录物品的价值intweight[1000];//记录物品的重量intb[1000];//记录此个排列的状态intk[1000];//记录最优解时候的排列状态voidRe(inti){if(im){if(bpv){for(j=1;j=m;j++)k[j]=b[j];v=bp;}return;3.贪心法：0-1背包问题与背包问