算法分析与设计实验报告.docx

文档介绍：安徽工业大学专业: 班级: 姓名: 学号: 实验一:回溯法完成 0-1 背包问题代码如下: #include "" #include<iostream> #include<cstdio> #include<> #include<iomanip> using namespace std; template<class ty> class Knap { public: friend void Init(); friend void Knapsack(); friend void Backtrack(int i); friend float Bound(int i); bool operator<(Knap<ty> a)const { if(fl<) return true; else return false; } private: ty w; // 重量 ty v; // 价值 float fl; // 单位重量的价值 v/w int kk; // 记录第几个物品 int flag; // 记录是否放入包中}; template<class ty> void Sort(Knap<ty> *li,int n) { int i,j,k; Knap<ty> minl; for(i=1;i<n;i++) { minl=li[0]; k=0; for(j=1;j<=n-i;j++) { if(minl<li[j]) { minl=li[j]; swap(li[j],li[k]); k=j; }}}} namespace jie // 命名空间{ int c=0,n=0; int *x=NULL; Knap<int> *bag=NULL; int cp=0,cw=0; int bestp=0; } using namespace jie; void Init() { int i=0; cout<<endl; cout<<" 请输入物品数量 n= "; cin>>n; cout<<endl; cout<<" 请输入背包容量 C= "; cin>>c; cout<<endl; bag=new Knap<int> [n]; x=new int[n]; cout<<" 请依次输入"<<n<<" 个物品的重量 W:"<<endl; for(i=0;i<n;i++) cin>>bag[i].w; cout<<endl; cout<<" 请依次输入"<<n<<" 个物品的价值 P:"<<endl; for(i=0;i<n;i++) cin>>bag[i].v; for(i=0;i<n;i++) { bag[i].flag=0; bag[i].kk=i; bag[i].fl=*bag[i].v/bag[i].w; } } void Backtrack(int i) { if(i>=n) // 到达叶节点{ bestp=cp; // 更新最优价值 return; } if(cw+bag[i].w<=c) // 进入左子树{ bag[i].flag=1; cw+=bag[i].w; cp+=bag[i].v; Backtrack(i+1); cw-=bag[i].w; cp-=bag[i].v; } if(Bound(i+1)>bestp)// 进入右子树{ bag[i].flag=0; Backtrack(i+1); }} // 计算当前节点处的上界 float Bound(int i) { int cleft = c-cw; // 剩余容量 float b= cp; while (i<n&&bag[i].w<=cleft) { // 以物品单位重量价值递减序装入 cleft-=bag[i].w ; b+=bag[i].v; i++; } // 装满背包 if (i<n) b+=*bag[i].v/bag[i].w * cleft; return b; } void Knapsack() // 计算最优解和变量值{ int L(0); //用L 累计价值,初始价值设置为 0 for(int k=0;k<n;k++) { x[bag[k].kk]=bag[k].flag; //x=0 表示未放入背包, x=1 表示放入背包 L+=bag[k].flag*bag[k].v; // 价值累加} cout<<endl; cout<<" 当前最优价值为:"<<L<<endl; cout<<" 变量值 x= "; for(int i=1;i<=n;i++) { cout<<x[i-1]; } delete []bag; bag=NULL; delete []x; x=NULL; cout<<endl; getch();