背包问题的三种解法代码实现.docx

《背包问题的三种解法代码实现.docx》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、背包问题的三种解法实验报告实验要求：分别用动态规划法、回溯法、分支限界法解决0/1背包问题，了解三种算法的算法步骤并上机实现。实验步骤：1.建立一个背包问题的解法类Bag.h。bag_m为动态规划法，bag_b为回溯法，bag_t为分支限界法。2.建立一个排序类Sort1.h。程序的需要对背包的价值比排序。3.由分支限界建立一个动态的最大堆及堆的各种操作和运算类SqList.h。代码实现：1.主函数：//背包问题的解法#include#include"Bag.h"//背包问题处理方法类usingn

2、amespacestd;intmain(){inti,n,M;cout<<"请输入物品个数：";cin>>n;double*m=newdouble[n+1];double*p=newdouble[n+1];cout<<"输入每个物品的重量：";for(i=1;i<=n;i++)cin>>m[i];cout<<"输入每个物品的价值：";for(i=1;i<=n;i++)cin>>p[i];cout<<"请输入背包的重量：";cin>>M;Bagbag;//创建一个背包问题的解法类对象cout<<"选择背包问题的解法，输

3、入1，动态规划法，输入2，回溯法，输入3，分支限界法。"<<''<<"请输入1或者2,或者输入3："<<"";cin>>i;if(i==1)bag.bag_m(m,p,n,M);//调用动态规划法if(i==2)bag.bag_b(m,p,n,M);//调用回溯法if(i==3)bag.bag_t(m,p,n,M);//调用分支限界法return0;}2.排序方法类：（Filename：Sort1.h）//合并排序类（合并排序）#includeusingnamespacestd;structo

4、bj{doublem;doublep;doublev;};typedefstructobjOBJ;//定义物体的数据结构classSort1{public:voidmerge_sort(OBJa[],intn)//以物体的价值比排序{inti,s,t=1;while(t

5、intr,intn){OBJ*bp=newOBJ[n];inti,j,k;i=p;j=q+1;k=0;while(i<=q&&j<=r){if(a[i].v<=a[j].v)bp[k++]=a[i++];elsebp[k++]=a[j++];}if(i==q+1){for(;j<=r;j++)bp[k++]=a[j];}else{for(;i<=q;i++)bp[k++]=a[i];}k=0;for(i=p;i<=r;i++)a[i]=bp[k++];deletebp;}};3.背包问题解法类：（Filename：B

6、ag.h）//背包问题方法类（包含三种方法）//bag_m动态规划法//bag_b回溯法//bag_t分支限界法#includeusingnamespacestd;#include"Sort1.h"#include"SqList.h"classBag{public:voidbag_m(double*m,double*p,intn,intM)//动态规划法{inti,j;int*x=newint[n+1];OBJ*objs=newOBJ[n+1];objs[0].m=0;objs[0].p=0;ob

7、js[0].v=0;for(i=1;i<=n;i++){objs[i].m=m[i];objs[i].p=p[i];objs[i].v=objs[i].m/objs[i].p;}double**optp;optp=newdouble*[n+1];for(i=0;i

8、M;j++){if(objs[i].m>j)optp[i][j]=optp[i-1][j];else{optp[i][j]=optp[i-1][j];if(optp[i][j]<(optp[i-1][int(j-objs[i].m)]+objs[i].p))optp[i][j]=(optp[i-1][int(j-objs[i].m)]+objs