算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告一、實(shí)驗(yàn)?zāi)康呐c要求：熟悉C/C++語(yǔ)言的集成開(kāi)發(fā)環(huán)境；通過(guò)本實(shí)驗(yàn)加深對(duì)貪心算法、動(dòng)態(tài)規(guī)劃和回溯算法的理解。二、實(shí)驗(yàn)內(nèi)容：掌握貪心算法、動(dòng)態(tài)規(guī)劃和回溯算法的概念和基本思想，分析并掌握"0-1"背包問(wèn)題的三種算法，并分析其優(yōu)缺點(diǎn)。三、實(shí)驗(yàn)題："0-1"背包問(wèn)題的貪心算法"0-1"背包問(wèn)題的動(dòng)態(tài)規(guī)劃算法"0-1"背包問(wèn)題的回溯算法四、實(shí)驗(yàn)步驟：1.理解算法思想和問(wèn)題要求；2.編程實(shí)現(xiàn)題目要求；3.上機(jī)輸入和調(diào)試自己所編的程序；4.驗(yàn)證分析實(shí)驗(yàn)結(jié)果；5.整理出實(shí)驗(yàn)報(bào)告。五、實(shí)驗(yàn)程序：1、“0-1”背包問(wèn)題的貪心算法源程序#include<iostream.h>structgoodinfo{floatp;//物品效益floatw;//物品重量floatX;//物品該放的數(shù)量intflag;//物品編號(hào)};//物品信息結(jié)構(gòu)體voidInsertionsort(goodinfogoods[],intn){intj,i;for(j=2;j<=n;j++){goods[0]=goods[j];i=j-1;while(goods[0].p>goods[i].p){goods[i+1]=goods[i];i--;}goods[i+1]=goods[0];}}//按物品效益，重量比值做升序排列voidbag(goodinfogoods[],floatM,intn){floatcu;inti,j;for(i=1;i<=n;i++)goods[i].X=0;cu=M;//背包剩余容量for(i=1;i<n;i++){if(goods[i].w>cu)//當(dāng)該物品重量大與剩余容量跳出break;goods[i].X=1;cu=cu-goods[i].w;//確定背包新的剩余容量}if(i<=n)goods[i].X=cu/goods[i].w;//該物品所要放的量/*按物品編號(hào)做降序排列*/for(j=2;j<=n;j++){goods[0]=goods[j];i=j-1;while(goods[0].flag<goods[i].flag){goods[i+1]=goods[i];i--;}goods[i+1]=goods[0];}cout<<"最優(yōu)解為:"<<endl;for(i=1;i<=n;i++){cout<<"第"<<i<<"件物品要放:";cout<<goods[i].X<<endl;}}voidmain(){cout<<"|--------運(yùn)用貪心法解背包問(wèn)題---------|"<<endl;cout<<"|-------------------------------------|"<<endl;intj;intn;floatM;goodinfo*goods;//定義一個(gè)指針while(j){cout<<"請(qǐng)輸入物品的總數(shù)量：";cin>>n;goods=newstructgoodinfo[n+1];//cout<<"請(qǐng)輸入背包的最大容量：";cin>>M;cout<<endl;inti;for(i=1;i<=n;i++){goods[i].flag=i;cout<<"請(qǐng)輸入第"<<i<<"件物品的重量:";cin>>goods[i].w;cout<<"請(qǐng)輸入第"<<i<<"件物品的效益:";cin>>goods[i].p;goods[i].p=goods[i].p/goods[i].w;//得出物品的效益，重量比cout<<endl;}Insertionsort(goods,n);bag(goods,M,n);cout<<"press<1>torunagian"<<endl;cout<<"press<0>toexit"<<endl;cin>>j;}}2、“0-1”背包問(wèn)題動(dòng)態(tài)規(guī)劃算法遠(yuǎn)程序：#include<stdio.h>#defineMAX20intn,c,w[MAX],v[MAX],m[MAX][MAX]={0};voidknapsack(){inti,j;for(i=1;i<=n;i++)for(j=1;j<=c;j++) {m[i][j]=m[i-1][j]; if(j>=w[i-1]&&m[i-1][j-w[i-1]]+v[i-1]>m[i][j]) m[i][j]=m[i-1][j-w[i-1]]+v[i-1]; }}//顯示所取的物品及其重量（其中一個(gè)解）//對(duì)數(shù)組m的最后一列檢查來(lái)求解voiddisp(){ inti,j; i=n; while(m[i][c]==m[i-1][c])i--; while(i>0) { j=i-1; while(m[i][c]-m[j][c]!=v[i-1]&&j>0) j--; printf("%5d%5d\n",w[i-1],v[i-1]); i=j; }}voidmain(){ inti,j; printf("輸入物品種數(shù):");scanf("%d",&n); printf("輸入每種物品的重量與價(jià)值:\n"); for(i=0;i<n;i++) scanf("%d%d",&w[i],&v[i]); printf("輸入背包的總重量:\n");scanf("%d",&c); knapsack();disp(); printf("最大價(jià)值=%d\n",m[n][c]); for(i=0;i<=n;i++) { for(j=0;j<=c;j++) printf("%3d",m[i][j]); printf("\n");}}3、"0-1"背包問(wèn)題的回溯算法源程序：#include<iostream>usingnamespacestd;voidinput(int*number,int*weight,int*price){inti,n;cout<<"包的容量:";cin>>weight[0];cout<<"物品數(shù):";cin>>*number;cout<<"各物品的重量:";for(i=1;i<=*number;i++){cin>>weight[i];}cout<<"各物品的價(jià)值:";for(i=1;i<=*number;i++){cin>>price[i];}}voidbacktrack(intt,intn,int*weight,int*price,int*maxPrice,int*flag,int*nowWeight,int*nowPrice,int*x){inti;if(t>n){if(*nowWeight<=weight[0]&&*nowPrice>*maxPrice){*maxPrice=*nowPrice;flag[0]=0;for(i=1;i<=n;i++){if(x[i]){flag[++flag[0]]=i;}}}return;}else{for(i=0;i<=1;i++){x[t]=i;*nowWeight+=weight[t]*i;*nowPrice+=price[t]*i;backtrack(t+1,n,weight,price,maxPrice,flag,nowWeight,nowPrice,x);*nowWeight-=weight[t]*i;*nowPrice-=price[t]*i;}}}voidoutput(int*maxPrice,int*flag){inti;cout<<endl;cout<<"物品的最大價(jià)值為："<<*maxPrice<<endl;cout<<"選中的物品為：";for(i=1;i<=flag[0];i++){cout<<flag[i]<<"";}cout<<endl;}intmain(){inttemp1=0,temp2=-1,temp3=0,temp4=0;//這一行很重要!int*number=&temp1,weight[100],price[100];int*maxPrice=&temp2,flag[100],*nowWeight=&temp3,*nowPrice=&temp4,x[100];input(number,weight,price);backtrack(1,*number,weight,price,maxPrice,flag,nowWeight,nowPrice,x);output(maxPrice,flag);return0;}六、實(shí)驗(yàn)結(jié)果：1、貪心算法實(shí)驗(yàn)結(jié)果：2、動(dòng)態(tài)規(guī)劃法實(shí)驗(yàn)結(jié)果：3、回溯算法實(shí)驗(yàn)結(jié)果：七、實(shí)驗(yàn)分析：1、“0-1”背包問(wèn)題的貪心算法貪心算法（又稱(chēng)貪婪算法）是指，在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣泛的許多問(wèn)題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。在本問(wèn)題中，通過(guò)求出每件物品的單位效益來(lái)確定放入哪個(gè)物品，從而求出解。本題目第一件物品的單位效益為6，而第二件物品的單位效益為2，第三件物品的單位效益為4，按照升序排列，順序?yàn)椋?32，有因?yàn)楸嘲萘繛?，所以，重量為1的第一件物品可以放入。由于第三件物品的重量為2，所以只能放入一半，背包的容量就滿了，不能再放了。2、“0-1”背包問(wèn)題的動(dòng)態(tài)規(guī)劃算法

動(dòng)態(tài)規(guī)劃過(guò)程是：每次決策依賴(lài)于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移。一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來(lái)的，所以，這種多階段最優(yōu)化決策解決問(wèn)題的過(guò)程就稱(chēng)為動(dòng)態(tài)規(guī)劃。基本思想與分治法類(lèi)似，也是將待求解的問(wèn)題分解為若干個(gè)子問(wèn)題（階段），按順序求解子階段，前一子問(wèn)題的解，為后一子問(wèn)題的求解提供了有用的信息。在求解任一子問(wèn)題時(shí)，列出各種可能的局部解，通過(guò)決策保留那些有可能達(dá)到最優(yōu)的局部解，丟棄其他局部解。依次解決各子問(wèn)題，最后一個(gè)子問(wèn)題就是初始問(wèn)題的解。本題目中m[i][j]表示有i個(gè)物品，背包容量為j時(shí)的最優(yōu)解，通過(guò)knapsack函數(shù)用來(lái)尋找最優(yōu)解的值，自底向上地對(duì)每一個(gè)物品進(jìn)行運(yùn)算，都將把其放入與不放入背包兩種情況下背包的總價(jià)值作=進(jìn)行比較，然后選擇中值較大者作為當(dāng)前狀態(tài)下的最優(yōu)值，最后求出最優(yōu)值。在通過(guò)disp函數(shù)用來(lái)輸出動(dòng)態(tài)規(guī)劃法中的二維矩陣。3、“0-1”背包問(wèn)題的回溯算法回溯法(探索與回溯法)是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條