学步园

解01背包问题有很多种方法，就我知道的就有动态规划，回溯法，分支界限法这几种，下面就列出我的回溯法解法，以供参考

#include<iostream><br /> #include <algorithm><br /> using namespace std;</p> <p>class Knap<br /> {<br /> public:<br /> Knap(double *pp,double *ww,double cc,int nn)//构造函数<br /> {<br /> p=pp;<br /> w=ww;<br /> c=cc;<br /> n=nn;<br /> cw=0;<br /> cp=0;<br /> bestp=0;<br /> x=new int[n+1];<br /> bestx=new int[n+1];<br /> }<br /> double knapsack();//找最优值的函数。<br /> double Bound(int i);//边界函数<br /> void BackTrack(int i);//回溯函数<br /> void output()//输出最佳路径<br /> {<br /> for(int i=1;i<=n;i++)<br /> cout<<bestx[i]<<" ";<br /> cout<<endl;<br /> }<br /> private:<br /> double c;<br /> int n;<br /> double *w;<br /> double *p;<br /> double cw;<br /> double cp;<br /> double bestp;<br /> int *x;<br /> int *bestx;</p> <p>};</p> <p>void Knap::BackTrack(int i)<br /> {<br /> if(i>n)<br /> {<br /> if(cp>bestp)/*保证最优，这样下面的bestx就是最优的路径。*/<br /> {<br /> bestp=cp;<br /> for(int i=1;i<=n;i++)<br /> bestx[i]=x[i];<br /> }<br /> return;<br /> }<br /> if(cw+w[i]<=c)//left<br /> {<br /> x[i]=1;//记录进入坐子树<br /> cw+=w[i];<br /> cp+=p[i];<br /> BackTrack(i+1);<br /> cw-=w[i];<br /> cp-=p[i];<br /> }<br /> if(Bound(i+1)>bestp)//right<br /> {<br /> x[i]=0;//记录进入右子树<br /> BackTrack(i+1);<br /> }<br /> }</p> <p>class Object<br /> {<br /> public:<br /> int ID;<br /> double d;<br /> };</p> <p>int cmp(Object a,Object b)//定于排序类型。<br /> {<br /> return a.d>b.d;//降序<br /> }</p> <p>double Knap::Bound(int i)<br /> {</p> <p> Object *Q=new Object[n+1];<br /> int j;<br /> for(j=1;j<=n;j++)<br /> {<br /> Q[j].ID=j;<br /> Q[j].d=1.0*p[j]/w[j];<br /> }<br /> sort(Q+1,Q+n+1,cmp);/*对数组Q排序。按cmp()方式排序。这里要注意是从Q[1]开始而不是从Q开始*/<br /> /*<br /> for(j=1;j<=n;j++)<br /> cout<<Q[j].ID<<" ";<br /> cout<<endl;<br /> */</p> <p> double cleft=c-cw;<br /> double b=cp;<br /> while(i<=n&&w[Q[i].ID]<=cleft)<br /> {<br /> cleft-=w[Q[i].ID];<br /> b+=p[Q[i].ID];<br /> i++;<br /> }<br /> if(i<=n)<br /> b+=1.0*p[Q[i].ID]*cleft/w[Q[i].ID];/*如果不能完整装入一个物品，则可以装入部分。*/<br /> return b;</p> <p>}</p> <p>double Knap::knapsack()<br /> {<br /> /*分支判断，如果背包容量足够大，就不用再回溯搜索了。*/<br /> int i;<br /> double W=0;<br /> double P=0;<br /> for(i=1;i<=n;i++)<br /> {<br /> W+=w[i];<br /> P+=p[i];<br /> }<br /> if(W<=c)<br /> return P;<br /> /*如果背包容量不够大，则有最有的方案，使用回溯方法。*/<br /> BackTrack(1);<br /> return bestp;<br /> }</p> <p>int main()<br /> {<br /> int n=4;<br /> double c=7;//背包容量<br /> /*注意点，这里的数组p[]和w[]的第一个元素是-1，这是因为我在操作过程中都是从数组元素的1开始的，而我们知道数组中第一个元素是0号元素，所以我这里用-1填上*/<br /> double p[]={-1,9,10,7,4};//物品价值<br /> double w[]={-1,3,5,2,1};//物品重量</p> <p> Knap k=Knap(p,w,c,n);<br /> cout<<k.knapsack()<<endl;<br /> k.output();<br /> cout<<k.Bound(1)<<endl;//输出为22，是最大理想值<br /> return 1;<br /> }