实验四回溯算法和分支限界法

《实验四回溯算法和分支限界法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验四回溯算法和分支限界法0-1背包问题、实验冃的1、掌握0・1背包问题的回溯算法;2、进一步掌握回溯算法。二、实验内容给定n和物品和一人背包，物品i的重量是wi,其价值为vi,问如何选择装入背包的物品，使得装入背包的物品的总价值最大？三、实验步骤1、代码//HS_ALGcpp:Definestheentrypointfortheconsoleapplication.//#include#includeusingnamespacestd;//物体结构体typedefstruct{floatw;〃物品重量floatp;〃物品价值floatv;〃背包体积

2、intid;〃物品个数}OBJECT;〃比较两物品体积boolcmp(OBJECTa,OBJECTb){returna.v>b.v;intn,bool}floatknapsack_back(OBJECTob[],floatM,x[]){〃回溯法inti,k;floatw_cur,p_total,p_cur,w_est,p_est;bool*y=newbool[n+l];//计算物体的价值重量比for(i=0;i<=n;i++){ob[i].v=ob[i].p/ob[i].w;y[i]=false;}//按照物体的价值重量比降序排列sort(ob,ob+n,cmp);//初始化当前背包中的价值

3、、重量w_cur=p_cur二p_total=0;k=0;while(k>=0){w_est=w_cur;p_est=p_cur;//沿当前分支可能取得的最大价值for(i=k;ip_total){for(i=k;i

4、i]・wv二M){//可装入第i个物体w_cur=w_cur+ob[i].w;p_cur=p_

5、cur+ob[i].p;y[i]=true;}else{//不能装入第i个物体y[i]=false;break;}}if(i>=n){//n个物体已经全部装入if(p_cur>p_total){//更新当前上限p_total=p_cur;k=n;//保存可能的解for(i=0;i=0)&&(!y[i]))i—;//沿着右分支结点方向回溯直到左分支结点//到达根结点算法结束//修改当前值if(i

6、=ob[i].p;y[i]=false;k=i+1;搜索右分支子树}}}//deletey;returnp_total;}intmain(){intn;floatm;cout«H请输入背包载重cin»m;cout«n请输入物品个数：cin»n;OBJECT*ob二newOBJECT[n];{cout«HW输入物品的重量、价格:H«endl;for(inti=0;i

7、i=0;i