算法分析与设计实验报告大学论文 .doc

《算法分析与设计实验报告大学论文 .doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、安徽工业大学专业：班级：姓名：学号：实验一：回溯法完成0-1背包问题代码如下：#include"stdafx.h"#include#include#include#includeusingnamespacestd;templateclassKnap{public:friendvoidInit();friendvoidKnapsack();friendvoidBacktrack(inti);friendfloatBound(inti);booloperator<(Knapa)co

2、nst{if(flvoidSort(Knap*li,intn){inti,j,k;Knapminl;for(i=1;i

3、}}namespacejie//命名空间{intc=0,n=0;int*x=NULL;Knap*bag=NULL;intcp=0,cw=0;intbestp=0;}usingnamespacejie;voidInit(){inti=0;cout<>n;cout<>c;cout<[n];x=newint[n];cout<<"请依次输入"<

4、in>>bag[i].w;cout<>bag[i].v;for(i=0;i=n)//到达叶节点{bestp=cp;//更新最优价值return;}if(cw+bag[i].w<=c)//进入左子树{bag[i].flag=1;cw+=bag[i].w;cp+=bag[i]

5、.v;Backtrack(i+1);cw-=bag[i].w;cp-=bag[i].v;}if(Bound(i+1)>bestp)//进入右子树{bag[i].flag=0;Backtrack(i+1);}}//计算当前节点处的上界floatBound(inti){intcleft=c-cw;//剩余容量floatb=cp;while(i

6、b;}voidKnapsack()//计算最优解和变量值{intL(0);//用L累计价值，初始价值设置为0for(intk=0;k

7、ch();}intmain(){cout<

8、**********回溯法解0-1背包问题**********

9、"<#include#includevoidMergeSort(int*data,intx,inty,int*temp){intp,q,m,i=x;if(y-x>1){m=x+(