蛮力法动归贪心分支限界法解01背包问题

1、算法综合实验报告学号：1004121206姓名： 林一、实验内容：分别用蛮力、动态规划、贪心及分支限界法实现对0-1背包问题的求解，并至少用两个测试用例对所完成的代码进行正确性及效率关系上的验证。二、程序设计的基本思想、原理和算法描述：1、蛮力法1.1 数据结构注：结构体obj用来存放单个物品的价值和重量typedef struct objint w;物品的重量in t v;/物品的价值;1.2 函数组成void subset(i nt s10,i nt n):用来生成子集的函数void judge(i nt s10, obj obj,i nt mark,i nt n,i nt c):判断子集

2、的可行性in t getmax(i nt mark,i nt n,i nt &flag):求解问题的最优解void outputObj(i nt flag, int s10,i nt n):输出选择物品的情况1.3 输入/输出设计本程序通过键盘进行输入、屏幕进行输出1.4符号名说明符号说明S存放子集mark记录子集的可行性n物品的个数c物品的容量max记录背包所能产生的最大价值flag记录能产生最大价值的子集的编号1.5算法描述算法的伪代码描述如下：输入：背包的容量c,物品的个数n,n个物品的重量wn,价值vn 输出：装入背包的物品编号以及产生的最大价值1. 初始化最大价值 max=O,结果子

3、集s= ;2. 对集合1,2,n的每一个子集T,执行下述操作：2.1 初始化背包的价值v=0，背包的重量w=0;2.2 对子集t的每一个元素j2.2.1 女口果w+wjvc,贝U w=w+wj,v=v+vj;2.2.2 否则，转步骤2考察下一个子集；2.3 如果 maxc )4.1 将第 i 个物品放入背包 ,objecti.Num=1 ；4.2 c-=pron.Weight ；4.3 i+ ；5. 记录最后放入背包的物品的重量： objecti.Num=(double)C/objecti.Weight ；4、分支限界法4.1 数据结构 注：物品结构体，存放物品价值、重量、单位价值、物品编号等

4、信息 struct objint v;/物品价值int w;/物品重量double avg;/ 物品单位价值int id;/ 物品编号;注：结构体 node 用来存放节点表节点struct nodenode *parent,/父亲结点指针*next;/后继结点指针int level,/ 节点所处的层isin,/记录物品是否装入背包， 0 代表不装 ,1 代表装入cw,/当前背包已经装入的物品重量cv;/当前背包已经装入的物品价值double ub;/ 结点的上界值;4.2 函数组成int Partitio n(_Object r,i nt first,i nt en d);以数组第一个元素为准

5、对数组进行一次划分并返回基准元素的位置坐标void QuickSort(_Object r,i nt first, int en d);快速排序double Upb(i nt i,i nt cw,i nt cv);计算上界值node *nnoder(node * pare nt1,i nt isin 1,double ub1);生成一个新的结点void add node( node *n ode1);将结点添加到队列中node *n ext no de(); /取下一个结点void fen zjx();/分支界限法的主要实现函数void output();/4.3输入/输出设计用于输出物品的选

6、择情况及最优解本程序通过键盘进行输入、屏幕进行输出4.4符号名说明符号说明c背包的容量n物品的个数pro存放物品信息avg物品的单位价值量opv背包容量最优解popv指向最优解的指针level节点的层cw当前背包装载量cv当前背包价值ub节点的上界值isin记录当前结点物品是否放入背包flag物品原来位置(4) 算法描述 算法的伪代码描述如下： 输入：背包的容量 c, 物品的个数 n,n 个物品的信息 pron 输出：装入背包的物品标号和背包获得的最大价值1. 对输入的物品按照单位价值量递减的顺序进行排序2. 初 始 化 问 题 最 优 解 opv=0, 初 始 化 第 0 层 结 点 ， 计

7、 算 上 界 值 ub=Upb(0,0,0); 并设置该结点设为优先级队列的根结点3. 循环直到优先级队列为空3.1 如果取出当前结点位于第 n-1 层，则其子结点已是叶子结点， 判断子结点取值情况，若得到的解大于当前问题得到的最优解opv,贝皿置问题的最优解 opv3.2 如果取出当前结点层 level n-1对结点i的每个孩子结点x执行下列操作：321 如果结点x可能产生的最优解ubvopv,贝U丢弃该结点；322 否则估算该节点x的目标函数值ub,将结点加入队列；4. 将该结点对应的最优值输出，回溯求得最优解的各个分量三、源程序及注释：1 、蛮力法 #include #include u

8、sing namespace std；/ 物品typedef struct obj int w； int v；/ 生成子集void subset(int s10,int n)int i,j,m,k;for(i=0;i=0;j-)m=k%2;sij=m; k=k/2;/ 判断子集可行性void judge(int s10, obj obj,int mark,int n,int c) int i,j,v,w;for(i=0;ipow(2,n);i+)w=0;v=0;for(j=0;jn;j+)w+=objj.w*sij;v+=objj.v*sij;if(w=c)marki=v;elsemarki=

9、0;/ 求问题的最优解int getmax(int mark,int n,int &flag)int i,max;max=0;for(i=0;imax)max=marki;flag=i;return max;/ 输出选择物品的情况void outputObj(int flag,int s10,int n)cout 装入背包物品的编号为： for(int i=0;in;i+)if(sflagi=1)couti+1 ;coutendl;int main()int s102410,mark1024,n,max,c,flag;obj obj10;coutc;coutn;cout 请分别输入物品的重量：

10、 ;for(int i=0;iobji.w;cout 请分别输入物品的价值： ;for(i=0;iobji.v;subset(s,n);judge(s,obj,mark,n,c);max=getmax(mark,n,flag);outputObj(flag,s,n);cout 背包可容纳的最大价值为： maxendl;return 0;2、动态规划法#includeusing namespace std;/ 比较并返回两个数中的较大值int max(int i,int j)if(ij)return j;elsereturn i;/ 求解背包取得的最大值int KnapSack (int w,i

11、nt v,int x,int n,int c) int i,j,V1051005=0;for(i=0;i=n;i+)Vi0=0;/初始化第 0列for(j=0;j=c;j+)V0j=0;/初始化第 0行for(i=1;i=n;i+)for(j=1;j=c;j+)if(j0;i-)/if(VijVi-1j)xi=1;j=j-wi;else xi=0;return Vnc;int main()int c,n,w105,v105,x105,max;/xcoutc;coutn;cout 请分别输入物品的重量： for(int i=1;iwi;cout 请分别输入物品的价值： for( i=1;ivi;

12、max=KnapSack(w,v,x,n,c);cout 装入背包的物品编号为：for(i=1;i=n;i+)if(xi=1) couti ;coutendl;cout 背包可容纳的最大价值为： maxendl; return 0;3、贪心法 #include#includeusing namespace std;/ 物品结构体struct _Objectint Value;/ 物品价值int Weight;/ 物品重量double AveValue;/ 物品单位价值double Num;/ 物品可以放入的数量int key;/ 物品标号;/ 划分int Partition(_Object r

13、,int first,int end)int i=first,j=end;while(ij)while(irj.AveValue)j-;if(ij)_Object temp=ri;ri=rj;rj=temp;i+;while(irj.AveValue)i+;if(ij)_Object temp=ri;ri=rj;rj=temp;j-;return i;/ 快速排序void QuickSort(_Object r,int first,int end)int pivot;if(firstend)pivot=Partition(r,first,end);QuickSort(r,first,pivot

14、-1);QuickSort(r,pivot+1,end);为物品个数， Mdouble knaspsack(int n,int M,_Object object) /n 为背包容量int i;int C=M;double maxValue=0;for(i=0;objecti.WeightC;i+)objecti.Num=1;/ 初始化放入背包的物品为 0 maxValue+=objecti.Value;C=C-objecti.Weight;objecti.Num=(double)C/objecti.Weight;maxValue+=objecti.Num*objecti.Value;retur

15、n maxValue;int main()int n,c;_Object pro1001;coutc;coutn;cout 请分别输入物品的重量和价值： ;for(int i=0;iproi.Weightproi.Value; proi.AveValue=(double)proi.Value/proi.Weight; proi.Num=0;proi.key=i;QuickSort(pro,0,n-1);double maxValue=knaspsack(n,c,pro); cout 背包的可容纳的最大价值为： ; printf(%.2f,maxValue);coutendl;int k;cou

16、t 各个物品装入背包的重量分别为： ; for(k=0;kn;k+)for(int j=0;jn;j+)if(proj.key=k) / 找到原来顺序的物品编号 coutproj.Weight*proj.Num ;coutendl;return 0;4、分支限界法 #include #include #include #include #include using namespace std;/ 物品结构体struct obj int v;/物品价值int w;/物品重量double avg;/ 物品单位价值int id;/物品编号;/ 节点结构体struct nodenode *parent

17、,/ 父亲结点指针*next;/ 后继结点指针int level,/ 节点所处的层isin,/记录物品是否装入背包， 0 代表不装 ,1 代表装入cw,/当前背包已经装入的物品重量cv;/当前背包已经装入的物品价值double ub;/ 结点的上界值;/ 划分int Partition(obj r,int first,int end)int i=first,j=end;while(ij)while(irj.avg)j-;if(ij)obj temp=ri;ri=rj; rj=temp; i+;while(irj.avg) i+;if(ij)obj temp=ri;ri=rj; rj=temp;

18、j-;return i;/ 快速排序void QuickSort(obj r,int first,int end) int pivot;if(firstend) pivot=Partition(r,first,end); QuickSort(r,first,pivot-1);QuickSort(r,pivot+1,end);class fzjxprivate:node *front,/队首指针*first,/根节点指针*popv;/解结点指针double opv;/背包可产生的最大价值obj *pro;/物品int n,/物品个数c;/背包容量public:fzjx(obj *pro1,int

19、 w1,int n1 );fzjx();int *flag;double Upb(int i,int cw,int cv);/计算上界值node *nnoder(node * parent1,int isin1,double ub1);void addnode(node *node1);/ 将结点添加到队列中 node *nextnode(); /取下一个结点void fenzjx();void output();fzjx:fzjx(obj *pro1,int c1,int n1 ) int i;n=n1;c=c1;pro=new obj n; flag=new intn; for(i=0;i

20、next=NULL;opv=0;popv=new node1;popv=NULL;QuickSort(pro,0,n-1);fzjx:fzjx()deletefirst;deletefront;deletepopv;deletepro;double fzjx:Upb(int i,int cw,int cv)int cleft=c-cw;double v=(double)cv;if (iparent=parent1; node2-next=NULL; node2-level=(parent1-level)+1; node2-isin=isin1;node2-ub=ub1;if(isin1=1)

21、node2-cw=parent1-cw+proparent1-level.w; node2-cv=parent1-cv+proparent1-level.v ;elsenode2-cw=parent1-cw; node2-cv=parent1-cv;return(node2);void fzjx:addnode(node *node1)/ 将结点加入优先队列node *p=front-next,*next1=front;double ub=node1-ub;while(p!=NULL)if(p-ubnext=p;next1-next=node1;break;next1=p;p=p-next;

22、if(p=NULL)next1-next=node1; node * fzjx:nextnode()/ 取上限最大结点node *p=front-next; front-next=p-next; return(p);void fzjx:fenzjx()int i;double ub2;node *node3;first=new node1; /根结点first-parent=NULL; first-next=NULL;first-level=0; first-cw=0;first-cv=0; first-isin=0;ub2=Upb(0,0,0); first-ub=ub2;front-nex

23、t=first; while(front-next!=NULL)node3=nextnode(); i=node3-level;if(i=n-1)if(node3-cw+proi.wcv+proi.v)opv)opv=node3-cv+proi.v; popv=nnoder(node3,1,opv);if(node3-cv)opv)opv=node3-cv; popv=nnoder(node3,0,opv);if(icw+proi.wcw+proi.w,node3-cv+proi.v)opv) ub2=Upb(i,node3-cw+proi.w,node3-cv+proi.v);addnode

24、(nnoder(node3,1,ub2);ub2=Upb(i,node3-cw,node3-cv);if(ub2opv)addnode(nnoder(node3,0,ub2);void fzjx:output()int i;for(i=n-1;i=0;i-)flagproi.id=popv-isin; popv=popv-parent;cout 装入背包的物品编号为 : ;for(i=0;in;i+)if(flagi=1)couti+1 ;coutendl;: opvendl;cout 背包可以产生的最大价值是int main ()int c,n;int i=0;obj *pro1;coutc

25、;coutn;pro1 = new objn;cout 请分别输入物品的重量和价值 for(i=0;ipro1i.wpro1i.v;pro1i.avg=1.0*pro1i.v/pro1i.v; pro1i.id=i;fzjx fzjx(pro1,c,n);fzjx.fenzjx();fzjx.output();return 0;四、运行输出结果：1、蛮力法用例测试 1 ：用例测试2 :*E; Debiig01ba Banli. cze85Bu n 刀tl 值为值an 价 c 甘里数的的编大t 容个品品的最y 的的物物口旳的ke 包口艮人物舸卩 菲鸟输書容細 一入入乳杀背可ff i务入包 一 冃

26、P?41522、动态规划法用例测试1 :*C：kProer& FdlesVlicrosoft Visual SiudioMyPrcjjectslinDebugl135量值为值Dn :童Q A C 量数的能编大to 重个品品最y 的的韧物|的蛇 包口 B,m入入的纳y 4厕層勺容an 人弓可、1可S 刀分人包 隹焉隹侷佳輛隹冃F1用例测试2 :3、贪心法用例测试1:用例测试2:4、分支限界法用例测试1 :! 5 i 值畫： 价丄是 和：值 匚各 :;重号大 =编r 谷个品品的口的鬲生 巴口 X的产 遇豐r A.- 可入包rocess returned 0 0x0) execution tue : 20.1? s ress emu keu to continue用例测试2 :五、调试和运行程序过程中产生的问题及采取的措施：1问题：蛮力法解决0/1背包问题时，如何表示给定