回溯法解背包问题实验报告

1、实验4回溯法解0-1背包问题一 、实验要求1要求用回溯法求解0-1 背包问题；2要求交互输入背包容量，物品重量数组，物品价值数组；3要求显示结果。二 、实验仪器和软件平台仪器 ：带 usb 接口微机软件平台： WIN-XP + VC+6.0三 、实验源码#include "stdafx.h"#include<iostream>#include<cstdio>#include<conio.h>#include<iomanip>using namespace std;template<class ty>class Kn

2、appublic:friend void Init();friend void Knapsack();friend void Backtrack(int i);friend float Bound(int i);bool operator<(Knap<ty> a)constif(fl<a.fl)return true;elsereturn false;private:ty w;/重量ty v;/价值float fl;/单位重量的价值v/wint kk;/记录第几个物品int flag;/记录是否放入包中;template<class ty>void Sort

3、(Knap<ty> *li,int n)int i,j,k;Knap<ty> minl;for(i=1;i<n;i+)minl=li0;k=0;for(j=1;j<=n-i;j+)if(minl<lij)minl=lij;swap(lij,lik);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

4、;cout<<" 请输入物品数量n = "cin>>n; cout<<endl;cout<<" 请输入背包容量C = "cin>>c; cout<<endl;bag=new Knap<int> n;x=new intn;cout<<" 请依次输入 "<<n<<" 个物品的重量W:"<<endl;for(i=0;i<n;i+)cin>>bagi.w;cout<&l

5、t;endl;cout<<" 请依次输入 "<<n<<" 个物品的价值P:"<<endl;for(i=0;i<n;i+)cin>>bagi.v;for(i=0;i<n;i+)bagi.flag=0;bagi.kk=i;bagi.fl=1.0*bagi.v/bagi.w;void Backtrack(int i)if(i>=n) /到达叶节点bestp=cp; /更新最优价值return;if(cw+bagi.w<=c) /进入左子树bagi.flag=1; cw+=bag

6、i.w;cp+=bagi.v; Backtrack(i+1);cw-=bagi.w; cp-=bagi.v;if(Bound(i+1)>bestp)/进入右子树bagi.flag=0; Backtrack(i+1);/ 计算当前节点处的上界float Bound(int i)int cleft = c-cw; /剩余容量float b = cp;while (i<n&&bagi.w<=cleft)/ 以物品单位重量价值递减序装入cleft-=bagi.w ;b+=bagi.v;i+;/ 装满背包if (i<n) b+=1.0*bagi.v/bagi.w

7、* cleft;return b;void Knapsack() /计算最优解和变量值int L(0);/用 L 累计价值，初始价值设置为0for(int k=0;k<n;k+)xbagk.kk=bagk.flag; /x=0表示未放入背包，x=1 表示放入背包L+=bagk.flag*bagk.v; /价值累加cout<<endl;cout<<" 当前最优价值为 :"<<L<<endl;cout<<" 变量值 x = "for(int i=1;i<=n;i+)cout<<xi-1;delete bag; bag=NULL;delete x; x=NULL;cout<<endl; getch();int main()cout<<endl;cout<<"|*回溯法解 0-1 背包问题 *|"<<endl;Init();Backtrack(0);Knapsack();return 0;四 、运行结果五 、实验小结通过该实验， 我充分了解了回溯法与分支界限法的区别。