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

兰州交通大学数理与软件工程学院题目0-1背包问题算法实现院系数理院专业班级信计09学生姓名雷雪艳学号200905130指导教师李秦二Ｏ一二年六月五日一、问题描述：1、0—1背包问题：给定n种物品和一个背包，背包最大容量为M，物品i的重量是wi,其价值是平Pi，问应当如何选择装入背包的物品，似的装入背包的物品的总价值最大？背包问题的数学描述如下：2、要求找到一个n元向量(x1，x2…xn)，在满足约束条件：10iiixMwx情况下，使得目标函数pxiimax，其中，1in；M0；wi0；pi0。满足约束条件的任何向量都是一个可行解，而使得目标函数达到最大的那个可行解则为最优解[1]。给定n种物品和1个背包。物品i的重量是wi，其价值为pi，背包的容量为M。问应如何装入背包中的物品，使得装人背包中物品的总价值最大？在选择装人背包的物品时，对每种物品i只有两种选择，即装入背包、不装入背包。不能将物品i装人背包多次，也不能只装入部分的物品i。该问题称为0-1背包问题。0-1背包问题的符号化表示是，给定M0，wi0，pi0，1in，要求找到一个n元0-1向量向量(x1，x2…xn)，Xi=0或1,1in,使得Mwxii，而且pxii达到最大[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、算法设计如下：#includeiostream.h#definemax100//最多物品数voidsort(intn,floata[max],floatb[max])//按价值密度排序{intj,h,k;floatt1,t2,t3,c[max];for(k=0;kn;k++)c[k]=a[k]/b[k];for(j=0;jn;j++)if(c[j]c[j+1]){t1=a[j];a[j]=a[j+1];a[j+1]=t1;t2=b[j];b[j]=b[j+1];b[j+1]=t2;t3=c[j];c[j]=c[j+1];c[j+1]=t3;}}voidknapsack(intn,floatlimitw,floatv[max],floatw[max],intx[max]){floatc1;//c1为背包剩余可装载重量inti;sort(n,v,w);//物品按价值密度排序c1=limitw;for(i=0;in;i++){if(w[i]c1)break;x[i]=1;//x[i]为1时，物品i在解中c1=c1-w[i];}}voidmain(){intn,i,x[max];floatv[max],w[max],totalv=0,totalw=0,limitw;cout请输入n和limitw:;cinnlimitw;for(i=1;i=n;i++)x[i]=0;//物品选择情况表初始化为0cout请依次输入物品的价值：endl;for(i=1;i=n;i++)cinv[i];coutendl;cout请依次输入物品的重量：endl;for(i=1;i=n;i++)cinw[i];coutendl;knapsack(n,limitw,v,w,x);couttheselectionis:;for(i=1;i=n;i++){coutx[i];if(x[i]==1){totalw=totalw+w[i];totalv=totalv+v[i];}}coutendl;cout背包的总重量为：totalwendl;//背包所装载总重量cout背包的总价值为：totalvendl;//背包的总价值}4、贪心算法运行结果如下图所示：方案二：动态规划算法1、动态规划的基本原理与分析动态规划算法的基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。它把已知问题分为很多子问题，按顺序求解子问题，在每一种情况下，列出各种情况的局部解，按条件从中选取那些最有可能产生最佳的结果舍弃其余。前一子问题为后面子问题提供信息，而减少计算量，最后一个子问题的解即为问题解。采用此方法求解0-1背包问题的主要步骤如下：①分析最优解的结构：最有子结构性质；②建立递归方程；③计算最优值；④构造最优解[4]。2、0-1背包问题的实现①最优子结构性质0-1背包问题具有最优子结构性质。设(y1，y2…yn)是所给0-1背包问题的一个最优解，则(y2，y3…yn)是下面相应子问题的一个最优解：nikkkxvmaxnkixjxwknikkk},1,0{因若不然，设(z2，z3…zn)是上述问题的一个最优解，而(y2，y3…yn)不是它的最优解，由此可见ni2niiiyv2,且niiizw2w1y1c。因此niiizv2v1y1niiiyv1niiizw2w1y1c这说明(y1，z2…zn)是所给0-1背包问题的一个更优解，从而(y1，y2…yn)不是所给0-1背包问题的最优解。此为矛盾[1]。②递归关系设所给0-1背包问题的子问题nikkkxvmaxnkixjxwknikkk},1,0{的最优值为m(i,j)，即m(i,j)是背包容量为j，可选择物品为i，i+1，……，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i,j)的递归式如下：wjjjimwijviwijimjim0),,1(},),1(),),1(max{j)m(i,wnjwnvnj0j)m(n,3、算法设计如下：#includeiostream#includeiomanipusingnamespacestd;constintMAX=1000;intw[MAX],v[MAX],best[MAX];intV[MAX][MAX];//最大价值矩阵intW,n;//W为背包的最大载重量，n为物品的数量//求最大值函数intmax(intx,inty){returnx=y?x:y;}//求最小值函数intmin(intx,inty){returnx=y?y:x;}voidKnaspack(){intMax=min(w[n]-1,W);for(intj=1;j=Max;j++)V[n][j]=0;for(j=w[n];j=W;j++)V[n][j]=v[n];for(inti=n-1;i1;i--){Max=min(w[i]-1,W);for(j=1;j=Max;j++)V[i][j]=V[i+1][j];for(j=w[i];j=W;j++)V[i][j]=max(V[i+1][j],V[i+1][j-w[i]]+v[i]);}V[1][W]=V[2][W];//先假设第一个物品不放入if(Ww[1])V[1][W]=max(V[1][W],V[2][W-w[1]]+v[1]);}//生成向量数组，决定某一个物品是否应该放入背包voidTraceback(){for(inti=1;in;i++)//比较矩阵两邻两行(除最后一行)，背包容量为W的最优值.{if(V[i][W]==V[i+1][W])//如果当前行的最优值与下一行的最优值相等，则表明该物品不能放入。best[i]=0;else//否则可以放入{best[i]=1;W-=w[i];}}best[n]=(V[n][W])?1:0;}voidmain(){cout输入商品数量n和背包容量W:;cinnW;cout输入每件商品的重量w:endl;for(inti=1;i=n;i++)cinw[i];memset(V,0,sizeof(V));cout输入每件商品的价值v:endl;for(i=1;i=n;i++)cinv[i];Knaspack();//构造矩阵Traceback();//求出解的向量数组inttotalW=0;inttotalV=0;//显示可以放入的物品cout所选择的商品如下:endl;cout序号i:重量w:价格v:endl;for(i=1;i=n;i++){if(best[i]==1){totalW+=w[i];totalV+=v[i];coutsetiosflags(ios::left)setw(5)iw[i]v[i]endl;}}cout放入的物品重量总和是:totalW价值最优解是:V[1][W]totalVendl;}4、计算复杂性分析利用动态规划求解0-1背包问题的复杂度为0(min{nc,2n}。动态规划主要是求解最优决策序列，当最优决策序列中包含最优决策子序列时，可建立动态规划递归方程，它可以帮助高效地解决问题[8]。5、动态规划运行结果如下图所示：方案三：回溯法1、回溯法的基本原理与分析回溯是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间，这个解空间必须至少包含问题的一个解(可能是最优的)。回溯法需要为问题定义一个解空间，这个解空间必须至少包含问题的一个解(可能是最优的)。使用递归回溯法解决背包问题的优点在于它算法思想简单，而且它能完全遍历搜索空间，肯定能找到问题的最优解奉但是由于此问题解的总组合数有n2个，因此随着物件数n的增大，其解的空间将以nn2级增长，当n大到一定程度上，用此算法解决背包问题将是不现实的。下一步是组织解空间以便它能被容易地搜索。典型的组织方法是图或树。一旦定义了解空间的组织方法，这个空间即可按照深度优先的方法从开始结点进行搜索，利用限界函数避免移动到不可能产生解的子空间。2、0-1背包问题的实现回溯法是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间，这个解空间必须至少包含问题的一个解(可能是最优的)。一旦定义了解空间的组织方要选择一个对象的子集，将它们装人背包，以便获得的收益最大，则解空间应组织成子集树的形状。首先形成一个递归算法，去找到可获得的最大收益。然后，对该算法加以改进，形成代码。改进后的代码可找到获得最大收益时包含在背包中的对象的集合。左子树表示一个可行的结点，无论何时都要移动到它，当右子树可能含有比当