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

《回溯法解0-1背包问题实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验4回溯法解0-1背包问题一、实验要求1．要求用回溯法求解0-1背包问题；2．要求交互输入背包容量，物品重量数组，物品价值数组；3．要求显示结果。二、实验仪器和软件平台仪器：带usb接口微机软件平台：WIN-XP+VC++6.0三、实验源码#include"stdafx.h"#include#include#include#includeusingnamespacestd;templateclassKnap{public:friendvoidInit();friendvoidKnaps

2、ack();friendvoidBacktrack(inti);friendfloatBound(inti);booloperator<(Knapa)const{if(flvoidSort(Knap*li,intn){inti,j,k;Knapminl;for(i=1;i

3、li[0];k=0;for(j=1;j<=n-i;j++){if(minl*bag=NULL;intcp=0,cw=0;intbestp=0;}usingnamespacejie;voidInit(){inti=0;cout<>n;cout<>c;cout<

4、ewKnap[n];x=newint[n];cout<<"请依次输入"<>bag[i].w;cout<>bag[i].v;for(i=0;i=n)//到达叶节点{bestp=cp;/

5、/更新最优价值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);}}//计算当前节点处的上界floatBound(inti){intcleft=c-cw;//剩余容量floatb=cp;while(i

6、=bag[i].w;b+=bag[i].v;i++;}//装满背包if(i

7、i<=n;i++){cout<

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

9、"<