回溯法解0-1背包问题实验报告.docVIP

实验4 回溯法解0-1背包问题 一 、实验要求 要求用回溯法求解0-1背包问题； 要求交互输入背包容量，物品重量数组，物品价值数组； 要求显示结果。 二 、实验仪器和软件平台 仪器 ：带usb接口微机 软件平台：WIN-XP + VC++6.0 三 、实验源码 #include stdafx.h #includeiostream #includecstdio #includeconio.h #includeiomanip using namespace std; templateclass ty class Knap { public: friend void Init(); friend void Knapsack(); friend void Backtrack(int i); friend float Bound(int i); bool operator(Knapty a)const { if(fla.fl) return true; else return false; } private: ty w; //重量 ty v; //价值 float fl; //单位重量的价值v/w int kk; //记录第几个物品 int flag; //记录是否放入包中 }; templateclass ty void Sort(Knapty *li,int n) { int i,j,k; Knapty minl; for(i=1;in;i++) { minl=li[0]; k=0; for(j=1;j=n-i;j++) { if(minlli[j]) { minl=li[j]; swap(li[j],li[k]); k=j; } } } } namespace jie //命名空间 { int c=0,n=0; int *x=NULL; Knapint *bag=NULL; int cp=0,cw=0; int bestp=0; } using namespace jie; void Init() { int i=0; coutendl; cout请输入物品数量 n = ; cinn; coutendl; cout请输入背包容量 C = ; cinc; coutendl; bag=new Knapint [n]; x=new int[n]; cout请依次输入n个物品的重量W:endl; for(i=0;in;i++) cinbag[i].w; coutendl; cout请依次输入n个物品的价值P:endl; for(i=0;in;i++) cinbag[i].v; for(i=0;in;i++) { bag[i].flag=0; bag[i].kk=i; bag[i].fl=1.0*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 (inbag[i].w=cleft) { //以物品单位重量价值递减序装入 cleft-=bag[i].w ; b+=bag[i].v; i++; } //装满背包 if (in) b+=1.0*bag[i].v/bag[i].w * cleft; return b; } void Knapsack() //计算最优解和变量值 { int L(0); //用L累计价值，初始价值设置为0 fo