算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告大學(xué)論文 .doc

《算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告大學(xué)論文 .doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、安徽工業(yè)大學(xué)專(zhuān)業(yè)：班級(jí)：姓名：學(xué)號(hào)：實(shí)驗(yàn)一：回溯法完成0-1背包問(wèn)題代碼如下：#include"stdafx.h"#include#include#include#includeusingnamespacestd;templateclassKnap{public:friendvoidInit();friendvoidKnapsack();friendvoidBacktrack(inti);friendfloatBound(inti);booloperator<(Knapa)co

2、nst{if(flvoidSort(Knap*li,intn){inti,j,k;Knapminl;for(i=1;i

3、}}namespacejie//命名空間{intc=0,n=0;int*x=NULL;Knap*bag=NULL;intcp=0,cw=0;intbestp=0;}usingnamespacejie;voidInit(){inti=0;cout<>n;cout<>c;cout<[n];x=newint[n];cout<<"請(qǐng)依次輸入"<

4、in>>bag[i].w;cout<>bag[i].v;for(i=0;i=n)//到達(dá)葉節(jié)點(diǎn){bestp=cp;//更新最優(yōu)價(jià)值return;}if(cw+bag[i].w<=c)//進(jìn)入左子樹(shù){bag[i].flag=1;cw+=bag[i].w;cp+=bag[i]

5、.v;Backtrack(i+1);cw-=bag[i].w;cp-=bag[i].v;}if(Bound(i+1)>bestp)//進(jìn)入右子樹(shù){bag[i].flag=0;Backtrack(i+1);}}//計(jì)算當(dāng)前節(jié)點(diǎn)處的上界floatBound(inti){intcleft=c-cw;//剩余容量floatb=cp;while(i

6、b;}voidKnapsack()//計(jì)算最優(yōu)解和變量值{intL(0);//用L累計(jì)價(jià)值，初始價(jià)值設(shè)置為0for(intk=0;k

7、ch();}intmain(){cout<

8、**********回溯法解0-1背包問(wèn)題**********

9、"<#include#includevoidMergeSort(int*data,intx,inty,int*temp){intp,q,m,i=x;if(y-x>1){m=x+(