《0-1背包问题四种不同算法的实现.doc》由会员分享，可在线阅读，更多相关《0-1背包问题四种不同算法的实现.doc（25页珍藏版）》请在金锄头文库上搜索。
1、兰州交通大学数理与软件工程学院题 目 0-1背包问题算法实现院 系 数理院 专业班级 信计09 学生姓名 雷雪艳 学 号 200905130 指导教师 李秦 二一二年 六 月 五 日一、问题描述： 1、01背包问题：给定n种物品和一个背包，背包最大容量为M，物品i的重量是wi,其价值是平Pi，问应当如何选择装入背包的物品，似的装入背包的物品的总价值最大？背包问题的数学描述如下：2、要求找到一个n元向量(x1，x2xn)，在满足约束条件：情况下，使得目标函数，其中，1in；M0；wi0；pi0。满足约束条件的任何向量都是一个可行解，而使得目标函数达到最大的那个可行解则为最优解1。 给定n 种物品
2、和1个背包。物品i 的重量是wi，其价值为pi，背包的容量为M。问应如何装入背包中的物品，使得装人背包中物品的总价值最大？在选择装人背包的物品时，对每种物品i只有两种选择，即装入背包、不装入背包。不能将物品i 装人背包多次，也不能只装入部分的物品i。该问题称为0-1背包问题。0-1背包问题的符号化表示是，给定M0， w i 0， pi 0，1in ，要求找到一个n元0-1向量向量(x1，x2xn)， X i =0 或1 , 1in, 使得 ，而且达到最大2。二、解决方案：方案一：贪心算法1、贪心算法的基本原理与分析 贪心算法总是作出在当前看来是最好的选择，即贪心算法并不从整体最优解上加以考虑，
3、它所作出的选择只是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它能产生整体最优解。在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好近似解。贪心算法求解的问题一般具有两个重要性质：贪心选择性质和最优子结构性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。2、0-1背包问
4、题的实现对于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#define max 100 /最多物品数void sort (
5、int n,float amax,float bmax) /按价值密度排序int j,h,k;float t1,t2,t3,cmax;for(k=0;kn;k+)ck=ak/bk;for(j=0;jn;j+)if(cjcj+1)t1=aj;aj=aj+1;aj+1=t1;t2=bj;bj=bj+1;bj+1=t2;t3=cj;cj=cj+1;cj+1=t3;void knapsack(int n,float limitw,float vmax,float wmax,int xmax)float c1; /c1为背包剩余可装载重量int i;sort(n,v,w); /物品按价值密度排序c1=l
6、imitw;for(i=0;ic1)break;xi=1; /xi为1时，物品i在解中c1=c1-wi;void main()int n,i,xmax;float vmax,wmax,totalv=0,totalw=0,limitw;coutn limitw;for(i=1;i=n;i+)xi=0; /物品选择情况表初始化为0cout请依次输入物品的价值：endl;for(i=1;ivi;coutendl;cout请依次输入物品的重量：endl;for(i=1;iwi;coutendl;knapsack (n,limitw,v,w,x);coutthe selection is:;for(i=
7、1;i=n;i+)coutxi;if(xi=1)totalw=totalw+wi;totalv=totalv+vi;coutendl;cout背包的总重量为：totalwendl; /背包所装载总重量cout背包的总价值为：totalvendl; /背包的总价值4、贪心算法运行结果如下图所示：方案二：动态规划算法1、动态规划的基本原理与分析动态规划算法的基本思想是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免
8、大量重复计算，从而得到多项式时间算法。它把已知问题分为很多子问题，按顺序求解子问题，在每一种情况下，列出各种情况的局部解，按条件从中选取那些最有可能产生最佳的结果舍弃其余。前一子问题为后面子问题提供信息，而减少计算量，最后一个子问题的解即为问题解。采用此方法求解0-1背包问题的主要步骤如下：分析最优解的结构：最有子结构性质；建立递归方程；计算最优值；构造最优解4。2、 0-1背包问题的实现 最优子结构性质0-1背包问题具有最优子结构性质。设(y1，y2yn)是所给0-1背包问题的一个最优解，则(y2，y3yn)是下面相应子问题的一个最优解：因若不然，设(z2，z3zn)是上述问题的一个最优解，
9、而(y2，y3yn)不是它的最优解，由此可见,且c。因此c这说明(y1，z2zn)是所给0-1背包问题的一个更优解，从而(y1，y2yn)不是所给0-1背包问题的最优解。此为矛盾1。 递归关系设所给0-1背包问题的子问题 的最优值为m(i,j)，即m(i,j)是背包容量为j，可选择物品为i，i+1，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i,j)的递归式如下：3、算法设计如下：#include#includeusing namespace std;const int MAX=1000;int wMAX,vMAX,bestMAX;int VMAXMAX; /
10、最大价值矩阵int W,n; /W为背包的最大载重量，n为物品的数量/求最大值函数int max(int x,int y) return x = y?x:y;/求最小值函数int min(int x,int y)return x= y ? y:x;void Knaspack()int Max=min(wn-1,W); for(int j=1; j = Max ; j+)Vnj=0;for( j=wn; j 1 ; i-)Max=min(wi-1,W);for( j=1; j = Max ; j+)Vij=Vi+1j;for( j=wi; j w1) V1W=max(V1W,V2W-w1+v1)
11、;/生成向量数组，决定某一个物品是否应该放入背包void Traceback()for(int i=1; i n ; i+) /比较矩阵两邻两行(除最后一行)，背包容量为W的最优值.if(ViW = Vi+1W) /如果当前行的最优值与下一行的最优值相等，则表明该物品不能放入。besti=0;else /否则可以放入besti=1;W-=wi;bestn=(VnW )?1:0;void main() coutnW;cout输入每件商品的重量w:endl;for(int i=1;iwi;memset(V,0,sizeof(V);cout输入每件商品的价值v:endl;for( i=1;ivi;K
12、naspack();/构造矩阵 Traceback(); /求出解的向量数组int totalW=0;int totalV=0;/显示可以放入的物品cout所选择的商品如下:endl;cout序号i:重量w:价格v:endl;for(i=1; i = n ; i+)if(besti = 1)totalW+=wi;totalV+=vi;coutsetiosflags(ios:left)setw(5)i wi viendl;cout放入的物品重量总和是:totalW 价值最优解是:V1W totalVendl;4、计算复杂性分析利用动态规划求解0-1背包问题的复杂度为0(minnc,2n。动态规划主要是求解最优决策序列，当最优
