综合设计性实验报告背包问题的多种算法设计与分析.doc

0-1背包问题的多种算法设计与分析一、实验内容和要求： 0-1背包问题是一例典型的组合优化的np完全问题。问题可以描述为：给定一组共n个物品，每种物品都有自己的重量wi, i=1n和价值vi, i=1n，在限定的总重量（背包的容量c）内，如何选择才能使得选择物品的总价值之和最高。选择最优的物品子集放置于给定背包中，最优子集对应n元解向量(x1,xn), xi0或1，因此命名为0-1背包问题。0-1背包问题是许多问题的原型，但它又是一个np完全问题。此实验主要研究和实现n(0=n=200)和c(c=2000, c为整数)都较大的情形，随机产生n个物品的重量向量wi(1=wi=100, wi为整数)和价值向量vi (1=vi=100, vi为整数)。0-1背包问题可以用许多方法来求解，有些算法可以得到问题的精确最优解，有些仅能获得一个近似最优解。本综合设计性实验要求用3种以上的方法求解0-1背包问题，获得精确最优解或近似最优解皆可，并对所采用的多种算法从运行时间、寻找是否为最优解、能够求解的问题规模等方面进行对比和分析。本课程讲述的算法思想都可以用来求解此问题，甚至本课程未涉及的许多算法也非常适合于求解此问题，学生可以先尝试先用本课程介绍的算法来实现和分析，学有余力或兴趣驱动下可以寻找一些智能算法的资料来试一试。涉及的方法可以有：蛮力求解、递归求解、动态规划求解、贪心求解、回溯法求解、广度优先的分支限界法求解，优先队列的启发式分支限界法、遗传算法、模拟退火算法、蚁群算法、粒子群算法等。为方便调试，采用文件输入，标准输出（或文件输出也可）的形式。数据输入的格式如下：每组测试数据包含n+1行，第1行为c和n，表示背包容量为c且有n个物品，接下来n行为这n个物品的重量wi和价值vi。背包容量和物品重量都为整数。n, c , wi, vi范围如上所述。输出两行。第一行为所选物品的最大价值之和，第二行为装入背包的物品所对应的n元最优解向量(x1,xn), xi0或1。二、多种算法详细设计1. 贪心算法 输入物品价值和重量。分别用数组vo.n和w0.n来记录。根据物品价值vi/wi由高到低对vo.n和w0.n进行排序。然后把物品从1到n依次加入背包,直到装不下为止。设c为背包容量，每次装一个物品，则c-=wi,当前价值为value+=vi,当c=wi =m（i+1，j） 0=j=wn =0 0=jwn 用二维数组mij存储m（i，j）的值。根据递归式算出mij的值。则m1c是给出所要求的0-1背包问题的最优值。相应的最优解可由算法traceback计算如下。如果m1c=m2c,则x1=0,否则x1=1.当x1=0时，由m2c继续构造最优解。当x1=1时，由m2c继续构造最优解。当x1=1时，由m2c-w1继续构造最优解。依次类推，可构造出相应的最优解（x1，x2，.，xn）。 void traceback(int *m,int n,int *w,int c,int *x)int i;if(m1c=m2c)x1=0;else x1=1;for(i=1;i=n-2;i+)if(xi=1)c-=wi;if(mi+1c=mi+2c)xi+1=0;else xi+1=1;if(mnc!=0)xn=1;3. 动态规划基于递归式的讨论，用二维数组m来存储m（i，j）的相应值，可设计解0-1背包问题的动态规划算法knapsack如下：templatevoid knapsack(type* v,int* w,int c,int n,type* m)int jmax=min(wn-1,c);for(int j=0;j=jmax;j+) mnj=0;for(j=wn;j1;i-)jmax=min(wi-1,c);for(j=0;j=jmax;j+) mij=mi+1j;for(j=wi;j=w1) m1c=max(m1c,m2c-w1+v1);template void traceback(type *m,int *w,int c,int n,int *x)fpr(int i=1;in;i+)if(mic=mi+1c) xi=0;else xi=1;c-=wi;xn=(mnc)?1:0;4. 回溯法求解 0-1背包问题是子集选取问题。一般情况下，0-1背包问题是np难的。0-1背包问题的解空间可用子集树表示。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当右子树中有可能包含最优解时才进入右子树搜索。否则将右子树剪去。设r是当前剩余物品价值总和；cp是当前价值；bestp是当前最优价值。计算右子树上界的方法是将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下去时，再装入该物品的一部分而装满背包。由此得到的价值是右子树中解的上界。为了计算上界，可先将物品依其单位重量价值从小到大排序，此后只要按顺序考察各物品即可。将物品依其单位价值排序的算法如下：class objectfriend int knapsack(int*,int*,int,int,int*);friend void sort(object*,int);public:int operator=a.d);private:int id;float d;/单位重量价值;void sort(object *q,int len) for(int i=0;ilen;i+) for(int j=0;jlen;j+) if(qi=qj) object temp=qi; qi=qj; qj=temp; 在实现时，由bound计算当前结点处的上界。类knap的数据成员记录解空间树中的结点信息，以减少参数传递及递归调用所需的栈空间。在解空间树的当前扩展结点处，仅当要进入右子树时才计算上界与其父节点的上界bound，以判断是否可将右子树剪去。进入左子树时不需要计算上界，因为其上界与其父结点的上界相同。在计算最优值的时候也要在另设一个数组bestx1.n来记录最优解，在backtrack算法中回溯得到bestx，当得到第一个最优值，若后面回溯到叶结点时值不大于当前最优值，则最优解bestx不改变。backtrack中得到最优值和最优解的算法如下：templatevoid knap:backtrack(int i)int flag;if(in)/到达叶节点flag=bestpcp;if(flag)bestp=cp;for(i=1;i=n;i+)bestxidi=xidi;return;if(cw+wibestp)/进入右子树xidi=0;backtrack(i+1);5. 分支界限法 在解0-1背包问题的优先队列式分支限界法中，活结点优先队列中结点元素n的优先级由该结点的上界函数bound计算出的值uprofit给出。上界函数与回溯法一样。子集树中以结点n为根的子树中任一结点的价值不超过n.profit。可用一个最大堆来实现活结点优先队列。堆中元素类型为heapnode。其私有成员有uprofit，profit，weight和level。对于任意活结点n，n.weight是结点n所相应的重量；n.profit是n所相应的价值；n.uprofit是结点n的价值上界，最大堆以这个值作为优先级。子集空间树中结点类型为bbnode。 类knap的成员bestx用来记录最优解。bestxi=1当且仅当最优解含有物品i。 算法maxknapsack实施对子集树的优先队列式分支限界搜索。 算法中e是当前扩展结点；cw是该结点所相应的重量；cp是相应的价值；up是价值上界。算法的while循环不断扩展结点，直到子集树的叶结点成为扩展结点时为止。此时优先队列中所有结点的价值上界均不超过该结点的价值。因此该叶结点相应的解为问题的最优解。 在while循环内部，算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。 建立最大堆maxheap，并对heapnode类中做相应修改，目的是为了使最大堆能根据n.uprofit值作相应调整。修改如下：templateclass heapnodefriend knap;public:int operator (heapnode a)const return uprofit (heapnode a)const return uprofita.uprofit;private:typep uprofit,/结点的价值上界profit;/结点所相应的价值typew weight;/结点所相应的重量int level;/活结点在子集树中所处的层序号bbnode *ptr;/指向活结点在子集树中相应结点的指针;3、 多种算法调试和测试1. 贪心算法 对于背包问题，贪心选择最终可得到最优解，但对于0-1背包问题，贪心选择无法保证最终能将背包装满，部分闲置的背包空间使单位背包空间的价值降低了。测试中数据基本与最优值相似，有的则相差较大。贪心算法得出的结不一定是最优解。2.递归求解 在编写递归的算法，最关键的就是怎样用二维数组来表示相应最优解的值，编写的时候需要注意传值。思路清晰，把数学的递归式用代码函数表示出来。 对于递归求解，算法简单，但消耗时间太长。在数据较少的情况下，可以很快得到正确结果，当数据达到35个数据的时候，需要较长时间，当数据达到40个以上的时候，由于时间太长则等待不出结果。可见递归的效率很低。 针对递归算法效率较低，可采用动态规划进行改进。3. 动态规划 采用动态规划算法，效率较高。用所提供的数据测试，均能很快得出正确结果。 在编写动态规划算法时，没有太大问题，只需要编写求出最大值和最小值的函数。还有回溯求最优解的算法。4. 回溯法求解 在编写该算法时首先遇到的第一个问题是要运用c+的一些语法，这对于只懂c的同学确实存在一下障碍。好在我们的小组成员有些人之前学过，所以在这方面问题不大，再加上不懂时通过网上查阅资料和相关书籍，问题很快就得到解决。 另外，就是在backtrack算法中求出最优值和最优解，每次当剩余的价值大于bestp，则进入右子树进行搜索。当到达叶结点时即得到一个最优值，把值赋给bestp，得到新的最优值。同时需记录最优解，此时把记录路径的数组x1.n的值赋给bestx1.n。 在记录最优解时需要注意一个问题。因为回溯的顺序是按照物品单位价值从高到低的顺序进行的，而输出的最优解则需要按照原顺序输出。所以在回溯中记录路径时，需注意记录的是原来次序下的路径，而不是排序后的路径。在这里我们在排序之前已经定义好一个类q。类中的数据成员id用来记录物品原来的位置。则排序后，物品原来的位置记录仍能被找到。则搜索到某个结点时，则xidi=1,否则xidi=0.5. 分支界限法 分支限界法的与回溯法不同的是前者是深度优先搜索，后者是广度优先搜索。分支限界法的效率会高些，但是需要建立一个最大堆作为优先队列。定义一个类maxheap来实现优先队列，定义如下：template class maxheap public: maxheap(t a, int size,int maxsize=50); maxheap(int maxsize=50); virtual maxheap(); void initialize(t arrays,int size,int array_size);/用数组对堆重新进行初始化 maxheap& insert( t value); maxheap& deletemax(t& value ); bool isempty()return currentsize=0?true:false; int size()return currentsize; void init(t a);private: void modifyup(int start); void modifydown(int start,int end);private: t *data; int maxsize; int currentsize;调试后小结：从编程到调试到可以运行中总会遇到各种各样的问题。在本次综合实验中我们一会颇深，在试验中我们学到了新知识，一些c+的语法，一些调试的技巧，以及根据纠错提示改错。同时也巩固了一些旧的知识，如文件的读写操作，输入输出。先把总结如下：(1) c+的语法，定于各种类，增加了程序可读性，是程序比较容易理解。同时在类中定义友元类或者友元函数，使类之间的某些操作不受限制，方便程序员的编写，完善功能。另外，类中的函数可在类中先申明，然后类在外定义，也是非常方便的。还有运算符的重载，以及类模板，函数模板的使用都增加了程序的可读性和易编写性。(2) 说来有点惭愧，在这次综合实验中，才真正学会vc的单步调试和断点，这给我们编写程序带来极大便利。另外通过查看每歩程序的输出，也可以方便的找出错误。(3) 这里是一些纠错提示： 1.c程序编译时出现warnning no newline at end of file。解决办法：在文件最后添加一个空白行。 2.link : fatal error lnk1168: cannot open debug/test.exe for writing解决办法： 打开任务管理器，将test.exe进程杀掉，然后重新编译链接 (4)数据的格式读入，由于数据很多，所以采用文件输入比较方便。file *fp;fp=fopen(d:bag.txt,r);/以读的方式打开文件if(!fp)printf(file cannot be opened);exit(1);fscanf(fp,%ld%ld,&c,&n);数据的文件格式输出file *ptr;ptr=fopen(d:result.txt, w);/以写的方式打开文件fprintf(ptr,%dn,value); for(i=1;i=n;i+)fprintf(ptr,%d %dn,i,xi); 最后还要关闭文件。fclose(fp);fclose(ptr);4、 多种算法对比算法运行时间/s（输入数据个数）是否为最优解能够求解问题规模2030401002001.贪心算法00000否-2.递归求解00.15614.07800是40+3.动态规划0000.0150.015是-4.回溯法00000.015是-5.分支限界法00000是-五、附录多种算法实现清单：带注释和功能模块说明的源程序清单：1.贪心算法#includeusing namespace std;void sort2(int n,int *v,int *w,int*& sort)int i,j,temp;for(i=2;i=n;i+)for(j=1;j=i;j+)if(vsorti/wi=1;i-)c-=wsorti;if(c=0)xsorti=1;value+=vsorti;else break;return value;int main()int n,c,i,value;file *fp;file *ptr;int *x,*w,*v,*sort;fp=fopen(d:bag.txt,r);/以读的方式打开文件if(!fp)printf(file cannot be opened);exit(1);fscanf(fp,%ld%ld,&c,&n);x=new intn+1;w=new intn+1;v=new intn+1;sort=new intn+1;for(i=1;i=n;i+)sorti=i; xi=0;for(i=1;i=n;i+)fscanf(fp,%ld%ld,&wi,&vi);sort2(n,v,w,sort);/从小到大value=greedy(n,w,v,x,c,sort);/调用函数ptr=fopen(d:result.txt, w);/以写的方式打开文件fprintf(ptr,%dn,value); for(i=1;i=n;i+)fprintf(ptr,%d %dn,i,xi); fclose(fp);fclose(ptr);return 0;2.递归求解#includeusing namespace std;int ma(int i,int j,int n,int *&m,int *w,int *v)int a,b,value;if(i=n) if(j=wn)value=vn;else value=0;return value;if(i=wi)mi+1j=ma(i+1,j,n,m,w,v);a=mi+1j;mi+1j-wi=ma(i+1,j-wi,n,m,w,v);/递归的调用b=mi+1j-wi+vi;if(ab)value=a;else value=b;return value;elsemi+1j=ma(i+1,j,n,m,w,v);/递归的调用value=mi+1j;return value;elsereturn 0; void traceback(int *m,int n,int *w,int c,int *x)int i;if(m1c=m2c)x1=0;else x1=1;for(i=1;i=n-2;i+)if(xi=1)c-=wi;if(mi+1c=mi+2c)xi+1=0;else xi+1=1;if(mnc!=0)xn=1;int main()int n,c,i;file *fp;file *ptr;int *x,*w,*v,*m;fp=fopen(d:bag.txt,r);/以读的方式打开文件if(!fp)printf(file cannot be opened);exit(1);fscanf(fp,%ld%ld,&c,&n);x=new intn+1;w=new intn+1;v=new intn+1;m=new int*n+1;for(i=1;i=n;i+)mi=new intc+1;xi=0;fscanf(fp,%ld%ld,&wi,&vi);for(i=1;i=wn)mni=vn;else mni=0;m1c=ma(1,c,n,m,w,v);/调用函数traceback(m,n,w,c,x);/调用函数ptr=fopen(d:result.txt, w);/以写的方式打开文件fprintf(ptr,%dn,m1c); for(i=1;i=n;i+)fprintf(ptr,%d %dn,i,xi); fclose(fp);/关闭文件fclose(ptr);/关闭文件return 0;3. 动态规划#includeusing namespace std;int min(int a,int b)if(ab)return a;else return b;templatevoid knapsack(type* v,int* w,int c,int n,type* m)int jmax=min(wn-1,c);for(int j=0;j=jmax;j+) mnj=0;for(j=wn;j1;i-)jmax=min(wi-1,c);for(j=0;j=jmax;j+) mij=mi+1j;for(j=wi;j=w1) m1c=max(m1c,m2c-w1+v1);template void traceback(type *m,int *w,int c,int n,int *x)fpr(int i=1;in;i+)if(mic=mi+1c) xi=0;else xi=1;c-=wi;xn=(mnc)?1:0; void traceback(int *m,int n,int *w,int c,int *x)int i;if(m1c=m2c)x1=0;else x1=1;for(i=1;i=n-2;i+)if(xi=1)c-=wi;if(mi+1c=mi+2c)xi+1=0;else xi+1=1;if(mnc!=0)xn=1;int main()int n,c,i;file *fp;file *ptr;int *x,*w,*v,*m;fp=fopen(d:bag.txt,r);/以只读的方式打开文件if(!fp)printf(file cannot be opened);exit(1);fscanf(fp,%ld%ld,&c,&n);x=new intn+1;w=new intn+1;v=new intn+1;m=new int*n+1;for(i=1;i=n;i+)mi=new intc+1;xi=0;fscanf(fp,%ld%ld,&wi,&vi);knapsack(v,w,c,n,m);traceback(m,n,w,c,x);ptr=fopen(d:result.txt, w);fprintf(ptr,%dn,m1c); for(i=1;i=n;i+)fprintf(ptr,%d %dn,i,xi); fclose(fp);fclose(ptr);/关闭两个文件return 0;4.回溯法求解#includeusing namespace std;templateclass knapfriend typep knapsack(typep*,typew*,typew,int,int*);private:typep bound(int i);void backtrack(int i);typew c;/背包容量int n;/物品总数typew *w;/物品重量数组typep *p;/物品价值数组int *x;int *id;typew cw;/当前装包重量typep cp;/当前装包价值typep bestp;/当前最优价值int *bestx;/*templatetypep knap:bound(int i)/计算结点所相应价值的上界int j;typep pp=cp;typew ww=cw;for(j=i;j=n;j+)ww+=wj;if(ww=c)pp+=pj;else break;ww-=wj;pp+=pj/(c-ww);return pp;*/templatetypep knap:bound(int i)/计算结点所相应价值的上界typew cleft=c-cw;typep b=cp;/以物品单位重量价值递减序装入物品while(i=n&wi=cleft)cleft-=wi;b+=pi;i+;/装填剩余容量装满背包if(i=n)b+=pi*cleft/wi;return b;templatevoid knap:backtrack(int i)int flag;if(in)/到达叶节点flag=bestpcp;if(flag)bestp=cp;for(i=1;i=n;i+)bestxidi=xidi;return;if(cw+wibestp)/进入右子树xidi=0;backtrack(i+1);class objectfriend int knapsack(int*,int*,int,int,int*);friend void sort(object*,int);public:int operator=a.d);private:int id;float d;/单位重量价值;void sort(object *q,int len) for(int i=0;ilen;i+) for(int j=0;jlen;j+) if(qi=qj) object temp=qi; qi=qj; qj=temp; /*void sort(object* q,int n)int i,j,temp;for(i=2;i=n;i+)for(j=1;j=i;j+)if(qi-1.dqj-1.d)temp=qi-1.id;qi-1.id=qj-1.id;qj-1.id=temp;*/templatetypep knapsack(typep p,typew w, typew c,int n,int *x)/返回最大价值，bestx返回最优解 typew w=0;/装包物品重量typep p=0;/装包物品价值 /定义依单位重量价值排序的物品数组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;/所有物品装包 /依单位重量价值排序sort(q,n); /创建类knap的数据成员knapk;k.p=new typepn+1;k.w=new typewn+1;k.id=new intn+1;k.x=new intn+1;for(i=1;i=n;i+)k.pi=pqi-1.id;k.wi=wqi-1.id;k.idi=qi-1.id;k.xi=0;k.cp=0;k.cw=0;k.c=c;k.n=n;k.bestp=0; /回溯搜索k.bestx=x;k.backtrack(1);deleteq;deletek.w;deletek.p;return k.bestp;int main()int n,c,i,value;file *fp;file *ptr;int *x,*w,*v;fp=fopen(d:bag.txt,r);if(!fp)printf(file cannot be opened);exit(1);fscanf(fp,%ld%ld,&c,&n);x=new intn+1;w=new intn+1;v=new intn+1;for(i=1;i=n;i+)xi=0;fscanf(fp,%ld%ld,&wi,&vi);value=knapsack(v,w,c,n,x);/coutvalueendl;int va=0;for(i=1;i=n;i+)if(xi)va+=vi;coutvaendl;ptr=fopen(d:result.txt, w);fprintf(ptr,%dn,value); for(i=1;i=n;i+)fprintf(ptr,%d %dn,i,xi); fclose(fp);fclose(ptr);return 0;5.分支界限法#includeusing namespace std;#include#ifndef maxheap_h#define maxheap_h template class maxheap public: maxheap(t a, int size,int maxsize=50); maxheap(int maxsize=50); virtual maxheap(); void initialize(t arrays,int size,int array_size);/用数组对堆重新进行初始化 maxheap& insert( t value); maxheap& deletemax(t& value ); bool isempty()return currentsize=0?true:false; int size()return currentsize; void init(t a);private: void modifyup(int start); void modifydown(int start,int end);private: t *data; int maxsize; int currentsize;templatemaxheap:maxheap(t a, int size,int maxsize) data=a;currentsize=size;maxsize=maxsize;for( int i=currentsize/2;i=1;i-)modifydown(i,currentsize);/-templatevoid maxheap:initialize(t arrays,int size,int array_size)if(data)delete data;data=arrays;currentsize=size;maxsize=array_size;for(int i=currentsize/2;i=1;i-)modifydown(i,currentsize);/-templatemaxheap:maxheap(int maxsize) /0号单元不用舍弃，数据从一号单元填入maxsize=maxsize;data=new tmaxsize+1;currentsize=0;/-template maxheap:maxheap() delete data; /-templatemaxheap& maxheap:insert(t value)if(currentsize=maxsize) cout错误:堆空间已满.endl; throw exception(堆空间已满);data+currentsize=value;modifyup(currentsize);/重新调整堆return *this; /-template maxheap& maxheap:deletemax( t& value )if(currentsize=0) cout错误:堆空.endl; throw exception(堆空);value=data1;data1=datacurrentsize-;