背包问题四种不同算法的实现

兰州交通大学数理与软件工程学院题目0-1背包问题算法实现院系数理院专业班级信计09学生姓名雷雪艳学号0指导教师李秦二Ｏ一二年六月五日一、问题描述：1、0—1背包问题：给定n种物品和一个背包，背包最大容量为M，物品i的重量是wi,其价值是平Pi，问应当如何选择装入背包的物品，似的装入背包的物品的总价值最大背包问题的数学描述如下：2、要求找到一个n元向量(x1，x2…xn)，在满足约束条件：情况下，使得目标函数，其中，1in；M>0；wi>0；pi>0。满足约束条件的任何向量都是一个可行解，而使得目标函数达到最大的那个可行解则为最优解[1]。给定n种物品和1个背包。物品i的重量是wi，其价值为pi，背包的容量为M。问应如何装入背包中的物品，使得装人背包中物品的总价值最大在选择装人背包的物品时，对每种物品i只有两种选择，即装入背包、不装入背包。不能将物品i装人背包多次，也不能只装入部分的物品i。该问题称为0-1背包问题。0-1背包问题的符号化表示是，给定M>0，wi>0，pi>0，1in，要求找到一个n元0-1向量向量(x1，x2…xn)，Xi=0或1,1in,使得，而且达到最大[2]。二、解决方案：方案一：贪心算法1、贪心算法的基本原理与分析贪心算法总是作出在当前看来是最好的选择，即贪心算法并不从整体最优解上加以考虑，它所作出的选择只是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它能产生整体最优解。在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好近似解。贪心算法求解的问题一般具有两个重要性质：贪心选择性质和最优子结构性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。2、0-1背包问题的实现对于0-1背包问题，设A是能装入容量为c的背包的具有最大价值的物品集合，则Aj=A-{j}是n-1个物品1,2,...,j-1,j+1,...,n可装入容量为c-wj的背包的具有最大价值的物品集合。用贪心算法求解0-1背包问题的步骤是，首先计算每种物品单位重量的价值vi/wi；然后，将物品进行排序，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总量未超过c，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直进行下去，直到背包装满为止。3、算法设计如下：#include<>#definemax100 { if(V[i][W]==V[i+1][W])n22n2nn2D=i;Q[i-1].d=*p[i]/w[i];P+=p[i];W+=w[i];}if(W<=c)returnP;<Q[j].d){f=Q[i].d;Q[i].d=Q[j].d;Q[j].d=f;}}KnapK;=newint[n+1];=newint[n+1];=newint[n+1];=newint[n+1];[0]=0;[0]=0;for(i=1;i<=n;i++){[i]=p[Q[i-1].ID];[i]=w[Q[i-1].ID];}=0;=0;=c;=n;=0;D=i; Q[i-1].d=(float)*p[i]/w[i]; P+=p[i]; W+=w[i]; } if(W<=c)returnP;<Q[j].d) { f=Q[i].d; Q[i].d=Q[j].d; Q[j].d=f; } } D]; [i]=w[Q[i-1].ID]; } =0; =0; =c; =n; D]=[j]; delete[]Q; delete[]; delete[]; delete[]; returnbestp;}voidmain(){ intm,n; inti=0,j=0; intp[100],w[20],x[20]; while(1) { cout<<"0-1背包问题——递归法"<<endl; cout<<"请输入背包的容量："<<endl;cout<<"请输入物品个数："<<endl; cout<<"请输入物品的重量："<<endl; cout<<"请输入物品的价值："<<endl;cout<<"背包的最优解为:"<<endl<<Knapsack(p,w,m,n,x)<<endl; cout<<"最优解条件下选择的背包为:"<<endl; for(i=1;i<=n;i++) cout<<x[i]<<"\t"; cout<<endl; }}4、运行结果如下图所示：三、四种算法的比较与分析这四种算法都得到了验证，运行结果证明了算法设计是可行的，正确的。通过对O-1背包问题的算法设计及时间复杂度分析可以看出。无论采用贪婪法还是动态规划法，都是在已知约束条件下求解最大值建立数学模型算法实现的过程；但算法具体实现和数据结构的建立要用到递归和栈操作。比较贪婪法和动态规划法。前者的时间复杂度低于后者，从耗费上而言优于后者。但后者的实现算法可读性要优于前者。动态规划算法的基本思想是把原问题分解为一系列子问题，然后从这些子问题中求出原问题的解。回溯其实就是穷举，穷举所有的解，找出解中最优的值。回溯法在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。回溯法的基本思路是：确定解空间，建立解空间树，用深度优先搜索算法递归搜索解空间树，并同时注意剪枝,常用的分枝一限界法有最小耗费法，最大收益法。FIFO(先进先出)法等。0-1背包问题的分枝一限界算法可以使用最大收益算法。该算法跟回溯法类似。但分枝限界法需要O()的解空间。故该算法不常用在背包问题求解。回溯法比分枝限界在占用内存方面具有优势。回溯法占用的内存是0(解空间的最大路径长度)，而分枝限界所占用的内存为0(解空间大小)。对于一个子集空间，回溯法需要0(n)的内存空间，而分枝限界则需要0(2n)的空间。虽然最大收益或最小耗费分枝限界在直觉上要好于回溯法，并且在许多情况下可能会比回溯法检查更少的结点，但在实际应用中，它可能会在回溯法超出允许的时间限制之前就超出了内存的限制。通过以上对0-1背包问题的求解分析，我们可以看到各种算法设计方法有各内不同的特点，针对不同的问题领域，它们有不同的效率，对于求解0-1背包问题，各算法的时间复杂度、优缺点以及改进方法的比较如下表所示：算法时间复杂度优点缺点改进方法动态规划O(min{nc,}）可求得最优决策序列速度较慢建立动态规划递归方程回溯法O(n）能够获得最优解时间复杂度较高判断右子树时，按效率密度vi/wi对剩余对象排序分枝-限界法O(）速度较快，易求解占用的内存较大，效率不高最大收益或最小消耗分枝-限界法，FIFO法贪心算法O(nlogn）可以达到局部最优解，用时少不能考虑到整体最优解，程序可读性低于动态规划对范围广的问题可以产生接近的最优解#include<>#include<iostream>#include<>#include<>#include<>#definemax100D=i;Q[i-1].d=*p[i]/w[i];P+=p[i];W+=w[i];}if(W<=c)returnP;<Q[j].d){f=Q[i].d;Q[i].d=Q[j].d;Q[j].d=f;}}KnapK;=newint[n+1];=newint[n+1];=newint[n+1];=newint[n+1];[0]=0;[0]=0;for(i=1;i<=n;i++){[i]=p[Q[i-1].ID];[i]=w[Q[i-1].ID];}=0;=0;=c;=n;=0;D=i; Q[i-1].d=(float)*p[i]/w[i]; P+=p[i]; W+=w[i]; } if(W<=c)returnP;<Q[j].d) { f=Q[i].d; Q[i].d=Q[j].d; Q[j].d=f; } } D]; [i]=w[Q[i-1].ID]; } =0; =0; =c; =n; D]=[j]; delete[]Q; delete[]; delete[]; delete[]; returnbestp;}voidmain3(){ intm,n; inti=0,j=0; intp[100],w[20],x[20]; while(1) { cout<<"0-1背包问题--递归法"<<endl; cout<<"请输入背包的容量："<<endl;cout<<"请输入物品个数："<<endl; cout<<"请输入物品的重量："<<endl; cout<<"请输入物品的价值："<<endl;cout<<"背包的最优解为:"<<endl<<Knapsack(p,w,m,n,x)<<endl; cout<<"最优解条件下选择的背包为:"<<endl; for(i=1;i<=n;i++) cout<<x[i]<<"\t"; cout<<endl; }}voidjiemian(){printf("\n");printf("\n");printf("\n");printf("\n");}//主函数intmain(){while(1){