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

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

2、end void Init();friend void Knapsack();friend void Backtrack(int i);friend float Bound(int i);bool operator<(Knap<ty> a)constif(fl<return true;else return false;private:ty w;cout<<endl;cout<<"请依次输入"<<n<<"个物品的价值P:"<<endl;for(i=0;i<n;i+)

3、cin>>bagi.v;for(i=0;i<n;i+)bagi.flag=0; bagi.kk=i;bagi.fl=*bagi.v/bagi.w;void Backtrack(int i)if(i>=n) <=c) lag=1; cw+=bagi.w;cp+=bagi.v; Backtrack(i+1);cw-=bagi.w; cp-=bagi.v;if(Bound(i+1)>bestp)lag=0; Backtrack(i+1);<=cleft)b+=bagi.v;i+;/bagi.w * cleft;return b;void Knapsack()

4、 k=bagk.flag; lag*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 背包问题*|&quo

5、t;<<endl;Init();Backtrack(0);Knapsack();return 0;四、运行结果法算机算法设计与分析 ,宾鳌t0K的实势T回溯法一.B *回溯法解"背包问题HMMMMXXKMXJ,输入物品数量n = 4I请输入背包容量C - 40I请依次输入4个物品的重量gI20 32 16 IS请依次输入4个物品的价值P:I100120 80当前最优价值为：2第I国里值x = 1010tPress dn少 ke9 to continue五、实验小结通过该实验，我充分了解了回溯法与分支界限法的区别。回溯法在问题的解 空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树 的