算法設(shè)計(jì)-1背包問題用動(dòng)態(tài)規(guī)劃的遞歸實(shí)現(xiàn)與非遞歸實(shí)現(xiàn)

1、華南農(nóng)業(yè)大學(xué)算法分析與設(shè)計(jì)課程實(shí)驗(yàn)專業(yè)年級(jí)：10信息與計(jì)算科學(xué)2班 學(xué)生學(xué)號(hào)： 22號(hào) 學(xué)生姓名： 梁高鼎 實(shí)驗(yàn)題目：用動(dòng)態(tài)規(guī)劃法求解0-1背包問題指導(dǎo)老師： 梁 茹 冰 實(shí)驗(yàn)時(shí)間： 2012年11月5日 一、實(shí)驗(yàn)內(nèi)容用動(dòng)態(tài)規(guī)劃法求解0-1背包問題 要求：(1)用遞歸實(shí)現(xiàn)（備忘錄方法） (2)用非遞歸實(shí)現(xiàn)（動(dòng)態(tài)規(guī)劃法）二、實(shí)驗(yàn)步驟 2.1、理解算法思想和問題要求； 2.2、寫出每個(gè)操作的算法2.2.1 遞歸實(shí)現(xiàn)（備忘錄方法）void find(int i,float tw,float tv)int k;/物品i包含在當(dāng)前方案的可能性if(tw+ai.weight <= limitW)co

2、pi=1;if(i<n-1)find(i+1,tw+ai.weight,tv);elsefor(k=0;k<n;+k)optionk=copk;maxv=tv;copi=0;/物品i不包含在當(dāng)前方案的可能性if(tv-ai.value>maxv)if(i<n-1)find(i+1,tw,tv-ai.value);elsefor(k=0;k<n;+k)optionk=copk;maxv=tv-ai.value;2.2.2 非遞歸實(shí)現(xiàn)（動(dòng)態(tài)規(guī)劃法）int knapsack(int &n,int &C,int sM,int pM,int VMM) int

3、 i,j; for (i=0;i<=n;i+) for(j=0;j<=C;j+) if(i=0|j=0) Vij=0; else if(si>j) Vij=Vi-1j; else if(si<=j) Vij=max(Vi-1j,Vi-1j-si+pi); return VnC; void traceback(int n,int C,int sM,int xM,int VMM) for(int i=1;i<=n;i+) if(ViC=Vi-1C) xi=0; else xi=1; C=C-si; 2.3、編程實(shí)現(xiàn)題目要求； 2.4、調(diào)試程序； 2.5、實(shí)驗(yàn)數(shù)據(jù)及實(shí)驗(yàn)

4、結(jié)果；2.5.1 遞歸方法：輸入數(shù)據(jù)：背包容量為50公斤。物品1重10公斤，價(jià)值60元；物品2重20公斤，價(jià)值100元；物品3重30公斤，價(jià)值120元。輸出結(jié)果：2.5.2 非遞歸方法：輸入數(shù)據(jù)：背包容量為50公斤。物品1重10公斤，價(jià)值60元；物品2重20公斤，價(jià)值100元；物品3重30公斤，價(jià)值120元。輸出結(jié)果： 2.6、算法時(shí)間復(fù)雜度 2.6.1 遞歸方法：O(n3) 2.6.2 非遞歸方法：O(n3)三、總結(jié) 通過本次實(shí)驗(yàn)，讓我意識(shí)到我對(duì)編程的不足,但也了解到自己的成長(zhǎng)空間還很大。 附錄：源代碼(1) 遞歸實(shí)現(xiàn)：#include <stdio.h>#define N 10

5、0 /最大物品總種數(shù)int n;/物品總種數(shù)float limitW;/限制的總重量float totV;/全部物品的總價(jià)值float maxv;/解的總價(jià)值int optionN;/解的選擇int copN;/當(dāng)前解的選擇struct /物品結(jié)構(gòu)float weight;float value;aN;void find(int i,float tw,float tv)int k;/物品i包含在當(dāng)前方案的可能性if(tw+ai.weight <= limitW)copi=1;if(i<n-1)find(i+1,tw+ai.weight,tv);elsefor(k=0;k<n;

6、+k)optionk=copk;maxv=tv;copi=0;/物品i不包含在當(dāng)前方案的可能性if(tv-ai.value>maxv)if(i<n-1)find(i+1,tw,tv-ai.value);elsefor(k=0;k<n;+k)optionk=copk;maxv=tv-ai.value;int main()int k;float w,v;printf("輸入物品種數(shù):");scanf("%d",&n);printf("輸入各物品的重量:");for(k=0;k<n;+k)scanf(&quo

7、t;%f",&w);ak.weight = w;printf("輸入各物品的價(jià)值:");for(totV=0.0,k=0;k<n;+k)scanf("%f",&v);ak.value = v;totV += v;printf("輸入限制重量:");scanf("%f",&limitW);maxv=0.0;for(k=0;k<n;+k)copk=0;find(0,0.0,totV);printf("選擇的物品:");for(k=0;k<n;+k)

8、printf("%d",optionk);printf("n總價(jià)值為: %f",maxv);getchar(); getchar() ; return 0; (2)非遞歸實(shí)現(xiàn)：#include<iostream>using namespace std;#define max(a,b) a>b?a:b#define M 100void display(int &n,int &C,int sM,int pM) int i; cout<<"please input n:" cin>>

9、n; cout<<endl; cout<<"please input tw:" cin>>C; cout<<endl; cout<<"please input w:"<<endl; s0=0; for(i=1;i<=n;i+) cin>>si; cout<<"please input v"<<endl; p0=0; for(i=1;i<=n;i+) cin>>pi;int knapsack(int &am

10、p;n,int &C,int sM,int pM,int VMM) int i,j; for (i=0;i<=n;i+) for(j=0;j<=C;j+) if(i=0|j=0) Vij=0; else if(si>j) Vij=Vi-1j; else if(si<=j) Vij=max(Vi-1j,Vi-1j-si+pi); return VnC; void traceback(int n,int C,int sM,int xM,int VMM) for(int i=1;i<=n;i+) if(ViC=Vi-1C) xi=0; else xi=1; C=

11、C-si; ;void main() int i,j,n,C; char ch; int sM,pM,xM; int VMM; while(1) display(n,C,s,p); cout<<"運(yùn)算結(jié)果如下："<<endl; for(i=1;i<=n;i+) xi=0; knapsack(n,C,s,p,V); cout<<" " for(j=0;j<=C;j+) cout<<j<<" " cout<<endl; for(i=0;i<=n;i+) cout<<i<<" " for(j=0;j<=C;j+) cout<<Vij<<" " cout<<endl; cout<<endl; cout<<"選擇的物體向量表示為:" cout<<" ( " traceback(n,C,s,x,V)