回溯算法解决背包问题_源代码

《回溯算法解决背包问题_源代码》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、templateclassKnap//建立类knap{friendTypewKnapsack(Typew*，Typew*，Typew，int);//友元函数的声明private://私有成员声明TypewBound(inti);voidBacktrack(inti);Typewc;//背包容量intn;//物品数Typew*w;//物品重量数组Typew*p;//物品价值数组Typewcw;//当前重量Typewcp;//当前价值Typewbestp

2、;//当前最优值};第二段templatevoidKnap::Backtrack(inti)//友元函数的定义{if(i>n){//到达叶结点bestp=cp;return;}if(cw+w[i]<=c)//搜索左子树{cw+=w[i];cp+=p[i];Backtrack(i+1);cw-=w[i];cp-=p[i];}if(Bound(i+1)>bestp)//搜索右子树Backtrack(i+1);}4第三段（重要）t

3、emplateTypepKnap::Bound(inti){//计算上界Typewcleft=c-cw;//剩余容量Typepb=cp;//以物品单位重量价值递减序装入物品while(i<=n&&w[i]<=cleft){cleft-=w[i];b+=p[i];i++;}//装满背包if(i<=n)b+=p[i]/w[i]*cleft;returnb;}第四段classObject{friendintKnapsack(int

4、*,int*,int,int);public:intoperator<=(Objecta)const{return(d>=a.d);}private:intID;//对象好floatd;//收益密度};第五段：templateTypew,Knapsack(tTypew,p[],Typew,w[],Typew,c,intn){//为Knap::Backtrack初始化Typew,W=0;Typew,P=0;Object*Q=newObject[n];f

5、or(inti=1;i<=n;i++){Q[i-1].ID=i;Q[i-1].d=1.0*p[i]/w[i];P+=p[i];W+=w[i];}4if(W<=c)returnP;//装入所有物品//依物品单位重量排序Sort（Q，n);KnapKK.p=newTypep[n+1];K.w=newTypep[n+1];K.x=newTypep[n+1];for(i=1;i<=n;i++){K.p[i]=p[Q[i-1].ID];K.w[i]=w[Q[i-1].ID];}K

6、.cp=0;K.cw=0;K.c=c;K.n=n;K.bestp=0;//回溯搜索K.Backtrack(1);delete[]Q;delete[]K.w;delete[]K.p;returnK.bestp;}补充voidmain(){int*p;int*w;intc=0;intn=0;inti=0;cout<<"请输入背包个数："<>n;p=newint[n+1];w=newint[n+1];p[0]=0;w[0]=0;4cout<<"请输入背包容量："<

7、>>c;cout<<"请依此输入每个物品的重量："<>w[i];cout<<"请依此输入每个物品的价值："<>p[i];cout<<"所能装入背包中总价值最大为"<