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

1、兰州交通大学数理与软件工程学院题 目 0-1背包问题算法实现院 系 数理院 专业班级 信计09 学生姓名 雷雪艳 学 号 指导教师 李秦 二一二年 六 月 五 日一、问题描述： 1、01背包问题：给定n种物品和一个背包，背包最大容量为M，物品i的重量是wi,其价值是平Pi，问应当如何选择装入背包的物品，似的装入背包的物品的总价值最大？背包问题的数学描述如下：2、要求找到一个n元向量(x1，x2xn)，在满足约束条件：情况下，使得目标函数，其中，1in；M0；wi0；pi0。满足约束条件的任何向量都是一个可行解，而使得目标函数达到最大的那个可行解则为最优解1。 给定n 种物品和1个背包。物品i

2、的重量是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背包问题的实现对于0-1背

4、包问题，设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 (int n,floa

5、t 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=limitw;for(

6、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=1;i=n;i+)c

7、outxi;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)是上述问题的一个最优解，而(y2，y3yn)

9、不是它的最优解，由此可见,且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; /最大价值矩阵int

10、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;Knaspack();

12、/构造矩阵 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。动态规划主要是求解最优决策序

13、列，当最优决策序列中包含最优决策子序列时，可建立动态规划递归方程，它可以帮助高效地解决问题8。5、动态规划运行结果如下图所示：方案三：回溯法1、回溯法的基本原理与分析回溯是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间，这个解空间必须至少包含问题的一个解(可能是最优的)。回溯法需要为问题定义一个解空间，这个解空间必须至少包含问题的一个解(可能是最优的)。使用递归回溯法解决背包问题的优点在于它算法思想简单，而且它能完全遍历搜索空间，肯定能找到问题的最优解奉但是由于此问题解的总组合数有个，因此随着物件数n的增大，其解的空间将以n级增长，当n大到一定程度上，用此算法解决背包

14、问题将是不现实的。下一步是组织解空间以便它能被容易地搜索。典型的组织方法是图或树。一旦定义了解空间的组织方法，这个空间即可按照深度优先的方法从开始结点进行搜索，利用限界函数避免移动到不可能产生解的子空间。2、 0-1背包问题的实现回溯法是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间，这个解空间必须至少包含问题的一个解(可能是最优的)。一旦定义了解空间的组织方要选择一个对象的子集，将它们装人背包，以便获得的收益最大，则解空间应组织成子集树的形状。首先形成一个递归算法，去找到可获得的最大收益。然后，对该算法加以改进，形成代码。改进后的代码可找到获得最大收益时包含在背包中

15、的对象的集合。左子树表示一个可行的结点，无论何时都要移动到它，当右子树可能含有比当前最优解还优的解时，移动到它。一种决定是否要移动到右子树的简单方法是r为还未遍历的对象的收益之和，将r加到cp (当前节点所获收益)之上，若( r+cp) bestp(目前最优解的收益)，则不需搜索右子树。一种更有效的方法是按收益密度vi/wi对剩余对象排序，将对象按密度递减的顺序去填充背包的剩余容量， 当遇到第一个不能全部放人背包的对象时， 就使用它的一部分。3、算法设计如下：#includeusing namespace std;class Knapfriend int Knapsack(int p,int

16、w,int c,int n );public:void print()for(int m=1;m=n;m+) coutbestxm ; coutendl;private:int Bound(int i);void Backtrack(int i);int c;/背包容量int n; /物品数int *w;/物品重量数组int *p;/物品价值数组int cw;/当前重量int cp;/当前价值int bestp;/当前最优值int *bestx;/当前最优解int *x;/当前解;int Knap:Bound(int i)/计算上界int cleft=c-cw;/剩余容量int b=cp;/以

17、物品单位重量价值递减序装入物品while(i=n&wi=cleft) cleft-=wi; b+=pi; i+;/装满背包if(in) if(bestpcp) for(int j=1;j=n;j+) bestxj=xj; bestp=cp;return;if(cw+wibestp)/搜索右子树 xi=0; Backtrack(i+1); class Objectfriend int Knapsack(int p,int w,int c,int n);public:int operator=a.d);private:int ID;float d;int Knapsack(int p,int w,

18、int c,int n)/为Knap:Backtrack初始化int W=0;int P=0;int i=1;Object *Q=new Objectn;for(i=1;i=n;i+)Qi-1.ID=i;Qi-1.d=1.0*pi/wi;P+=pi;W+=wi;if(W=c) return P;/装入所有物品/依物品单位重量排序float f;for( i=0;in;i+)for(int j=i;jn;j+) if(Qi.dQj.d) f=Qi.d; Qi.d=Qj.d; Qj.d=f; Knap K;K.p = new intn+1; K.w = new intn+1;K.x = new i

19、ntn+1;K.bestx = new intn+1;K.x0=0;K.bestx0=0;for( i=1;i=n;i+)K.pi=pQi-1.ID;K.wi=wQi-1.ID;K.cp=0;K.cw=0;K.c=c;K.n=n;K.bestp=0;/回溯搜索K.Backtrack(1); K.print(); delete Q;delete K.w;delete K.p;return K.bestp;void main()int *p;int *w; int c=0;int n=0;int i=0;char k;while(k)cout请输入背包容量(c)：c;cout请输入物品的个数(n)

20、：n;p=new intn+1;w=new intn+1;p0=0;w0=0;cout请输入物品的价值(p)：endl;for(i=1;ipi;cout请输入物品的重量(w)：endl;for(i=1;iwi;cout最优解为(bestx)：endl;cout最优值为(bestp)：endl;coutKnapsack(p,w,c,n)endl; couts 重新开始endl;coutq 退出k;4、运行结果如下图所示：方案四：分枝-限界法1、分枝-限界法的基本原理与分析 分枝限界发是另一种系统地搜索解空间的方法，它与回溯法的主要区别在于对E-结点(expansion node)的扩充方式。每个

21、活结点有且仅有一次会变成E-结点。当一个结点变为E-结点时，则生成从该结点移动一步即可到达的所有新结点。在生成的结点中，抛弃那些不可能导出(最优)可行解的结点，其余结点加人活结点表，然后从表中选择一个结点作为下一个E结点。从活结点表中取出所选择的结点并进行扩充，直到找到解或活动表为空，扩充才结束。2、0-1背包问题的实现0-1背包问题的最大收益分枝定界算法可以使用定界函数来计算活结点的收益上限upprofit，使得以活结点为根的子树中的任一结点的收益值都不可能超过upprofit，活结点的最大堆使用upprofit作为关键值域。在子集树中执行最大收益分枝定界搜索的函数首先初始化活结点的最大堆，

22、并使用一个数组bestx来记录最优解。由于需要不断地利用收益密度来排序，物品的索引值会随之变化，因此必须将函数所生成的结果映射回初始时的物品索引。函数中的循环首先检验E-结点左孩子的可行性，如它是可行的，则将它加入子集树及活结点队列(即最大堆)，仅当结点右子树的定界值指明可能找到一个最优解时才将右孩子加入子集树和队列中。3、算法设计： #include class Knap;class Object;class Objectfriend int Knapsack(int *,int *,int ,int ,int *);public:int operator = a.d);private:in

23、t ID;float d;/单位重量价值;class bbnodefriend Knap;friend int Kanpsack(int *,int *,int ,int ,int *);private:bbnode * parent;/指向父节点的指针bool LChild; /左儿子结点标志;class HeapNodefriend Knap;public:operator int () const return uprofit;void Insert(HeapNode N);void DeleteMax(HeapNode N);private:int uprofit, /结点的价值上界p

24、rofit; /结点所对应的价值 int weight; /结点所对应的重量int level; /活结点在子集树中所处的层序号bbnode * ptr; /指向活结点在子集树中相应结点的指针;void HeapNode:Insert(HeapNode N)void HeapNode:DeleteMax(HeapNode N)class Knapfriend int Knapsack(int *,int *,int ,int ,int *);public:int MaxKnapsack();private:HeapNode *H;int MaxBoundary(int i);void AddL

25、iveNode(int up,int cp,int cw,bool ch,int level);bbnode * E; /指向扩展结点的指针int c; /背包容量int n; /物品总数int *w; /物品重量数组int *p; /物品价值数组int cw; /当前背包重量int cp; /当前背包价值int * bestx; /最优解的记录数组;/计算所相应的价值的上界int Knap:MaxBoundary(int i)int cleft=c-cw; /剩余容量int b=cp; /价值上限/以物品单位重量价值递减序装填剩余容量while(i=n&wi=cleft)cleft-=wi;

26、b+=pi;i+;/将背包的剩余容量装满if(iparent=E;b-LChild=ch;HeapNode N;N.uprofit=up;N.profit=cp;N.weight=cw;N.level=lev;N.ptr=b;H-Insert(N);/实施对子集树的优先队列式分支界限搜索int Knap:MaxKnapsack()/优先队列式分支界限法，返回最大值，bestx返回最优解/定义最大堆的容量为1000H=new HeapNode 1000;/为bestx分配存储空间bestx=new int n+1;/初始化int i=1;E=0;cw=cp=0;int bestp=0; /当前最

27、优解int up=MaxBoundary(1);/价值上界/搜索子集空间树while(i!=n+1)/非叶结点/检查当前扩展结点的左儿子结点int wt=cw+wi;if(wtbestp)bestp=cp+pi;AddLiveNode(up,cp+pi,cw+wi,true,i+1);up=MaxBoundary(i+1);/检查当前扩展结点的右儿子结点if(up=bestp)AddLiveNode(up,cp,cw,false,i+1);/去下一个扩展结点HeapNode N;H-DeleteMax(N);E=N.ptr;cw=N.weight;cp=N.profit;up=N.uprofi

28、t;i=N.level;/构造当前最优解for(int j=n;j0;j-)bestxj=E-LChild;E=E-parent;return cp;/对数据进行预处理并完成调用MaxKnapsackint Knapsack(int p,int w,int c,int n,int bestx)/返回最大值，bestx返回最优解/初始化int W=0; /装包物品重量int P=0; /装包物品价值/定义依单位重量价值排序的物品数组Object * Q=new Objectn;for(int i=1;i=n;i+)/单位重量价值数组Qi-1.ID=i;Qi-1.d=(float)1.0*pi/w

29、i;P+=pi;W+=wi;if(W=c) return P;/所有物品装包/依单位重量价值排序float f;for( i=0;in;i+)for(int j=i;jn;j+)if(Qi.dQj.d)f=Qi.d;Qi.d=Qj.d;Qj.d=f;/创建类Knap的数据成员Knap K;K.p=new int n+1;K.w=new int n+1;for(i=1;i=n;i+)K.pi=pQi-1.ID;K.wi=wQi-1.ID;K.cp=0;K.cw=0;K.c=c;K.n=n;/调用MaxKnapsack求问题的最优解int bestp=K.MaxKnapsack();for(int

30、 j=1;j=n;j+)bestxQj-1.ID=K.bestxj;delete Q;delete K.w;delete K.p;delete K.bestx;return bestp;void main()int m,n;int i=0,j=0;int p100,w20,x20;while(1)cout0-1背包问题递归法endl; cout请输入背包的容量：endl;cout请输入物品个数：endl; cout请输入物品的重量：endl; cout请输入物品的价值：endl; cout背包的最优解为:endlKnapsack(p,w,m,n,x)endl; cout最优解条件下选择的背包为

31、:endl; for(i=1;i=n;i+) coutxit; coutendl;4、运行结果如下图所示： 三、四种算法的比较与分析这四种算法都得到了验证，运行结果证明了算法设计是可行的，正确的。通过对O-1背包问题的算法设计及时间复杂度分析可以看出。无论采用贪婪法还是动态规划法，都是在已知约束条件下求解最大值建立数学模型算法实现的过程；但算法具体实现和数据结构的建立要用到递归和栈操作。比较贪婪法和动态规划法。前者的时间复杂度低于后者，从耗费上而言优于后者。但后者的实现算法可读性要优于前者。动态规划算法的基本思想是把原问题分解为一系列子问题，然后从这些子问题中求出原问题的解。回溯其实就是穷举，

32、穷举所有的解，找出解中最优的值。回溯法在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。回溯法的基本思路是：确定解空间，建立解空间树，用深度优先搜索算法递归搜索解空间树，并同时注意剪枝,常用的分枝一限界法有最小耗费法，最大收益法。FIFO(先进先出)法等。0-1背包问题的分枝一限界算法可以使用最大收益算法。该算法跟回溯法类似。但分枝限界法需要O()的解空间。故该算法不常用在背包问题求解。回溯法比分枝限界在占用内存方面具有优势。回溯法占用的内存是0(解空间的最大路径长度)，而分枝限界所占用的内存为0(解空间大小)。对于一个子集空间，回溯法需要0(n)的内存空间，而分枝

33、限界则需要0(2n)的空间。虽然最大收益或最小耗费分枝限界在直觉上要好于回溯法，并且在许多情况下可能会比回溯法检查更少的结点，但在实际应用中，它可能会在回溯法超出允许的时间限制之前就超出了内存的限制。通过以上对0-1背包问题的求解分析，我们可以看到各种算法设计方法有各内不同的特点，针对不同的问题领域，它们有不同的效率，对于求解0-1背包问题，各算法的时间复杂度、优缺点以及改进方法的比较如下表所示：算法时间复杂度优点缺点改进方法动态规划O(minnc,）可求得最优决策序列速度较慢建立动态规划递归方程回溯法O(n）能够获得最优解时间复杂度较高判断右子树时，按效率密度vi/wi对剩余对象排序分枝-限

34、界法O(）速度较快，易求解占用的内存较大，效率不高最大收益或最小消耗分枝-限界法，FIFO法贪心算法O(nlogn）可以达到局部最优解，用时少不能考虑到整体最优解，程序可读性低于动态规划对范围广的问题可以产生接近的最优解#include#include#include#include#include #define max 100 /最多物品数void sort (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

35、=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; int i; /c1为背包剩余可装载重量sort(n,v,w); /物品按价值密度排序c1=limitw;for(i=0;ic1)break;xi=1; /xi为1时，物品i在解中c1=c1-wi;void main1()int n,i,xmax;float vmax,wmax,totalv=0,totalw=0,limi

36、tw;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=1;i=n;i+)coutxi;if(xi=1)totalw=totalw+wi;totalv=totalv+vi;coutendl;cout背包的总重量为：totalwendl; /背包所装载总重量cout背包的总价值为：to

37、talvendl; /背包的总价值using namespace std;class Knapfriend int Knapsack(int p,int w,int c,int n );public:void print()for(int m=1;m=n;m+) coutbestxm ; coutendl;private:int Bound(int i);void Backtrack(int i);int c;/背包容量int n; /物品数int *w;/物品重量数组int *p;/物品价值数组int cw;/当前重量int cp;/当前价值int bestp;/当前最优值int *best

38、x;/当前最优解int *x;/当前解;int Knap:Bound(int i)/计算上界int cleft=c-cw;/剩余容量int b=cp;/以物品单位重量价值递减序装入物品while(i=n&wi=cleft) cleft-=wi; b+=pi; i+;/装满背包if(in) if(bestpcp) for(int j=1;j=n;j+) bestxj=xj; bestp=cp;return;if(cw+wibestp)/搜索右子树 xi=0; Backtrack(i+1); class Objectfriend int Knapsack(int p,int w,int c,int

39、 n);public:int operator=a.d);private:int ID;float d;int Knapsack(int p,int w,int c,int n)/为Knap:Backtrack初始化int W=0;int P=0;int i=1;Object *Q=new Objectn;for(int i=1;i=n;i+)Qi-1.ID=i;Qi-1.d=1.0*pi/wi;P+=pi;W+=wi;if(W=c) return P;/装入所有物品/依物品单位重量排序float f;for( i=0;in;i+)for(int j=i;jn;j+) if(Qi.dQj.d)

40、 f=Qi.d; Qi.d=Qj.d; Qj.d=f; Knap K;K.p = new intn+1; K.w = new intn+1;K.x = new intn+1;K.bestx = new intn+1;K.x0=0;K.bestx0=0;for( i=1;i=n;i+)K.pi=pQi-1.ID;K.wi=wQi-1.ID;K.cp=0;K.cw=0;K.c=c;K.n=n;K.bestp=0;/回溯搜索K.Backtrack(1); K.print(); delete Q;delete K.w;delete K.p;return K.bestp;void main2()int

41、*p;int *w; int c=0;int n=0;int i=0;char k;while(k)cout请输入背包容量(c)：c;cout请输入物品的个数(n)：n;p=new intn+1;w=new intn+1;p0=0;w0=0;cout请输入物品的价值(p)：endl;for(i=1;ipi;cout请输入物品的重量(w)：endl;for(i=1;iwi;cout最优解为(bestx)：endl;cout最优值为(bestp)：endl;coutKnapsack(p,w,c,n)endl; couts 重新开始endl;coutq 退出k;class Knap;class Ob

42、ject;class Objectfriend int Knapsack(int *,int *,int ,int ,int *);public:int operator = a.d);private:int ID;float d;/单位重量价值;class bbnodefriend Knap;friend int Kanpsack(int *,int *,int ,int ,int *);private:bbnode * parent;/指向父节点的指针bool LChild; /左儿子结点标志;class HeapNodefriend Knap;public:operator int () const return uprofit;void Insert