算法設(shè)計與分析試驗報告01背包問題

1、算法設(shè)計分析實驗報告課程名稱：計算機算法設(shè)計分析專 業(yè)：班 級：學(xué) 號：姓 名： 指導(dǎo)教師:一、問題的提出問題描述：給定n種物品和一個背包。物品i的重量是wi,體積是bi ,其價 值為vi ,背包的容量為c,容積為d。問應(yīng)如何選擇裝入背包中的物 品，使得裝入背包中物品的總價值最大 ？在選擇裝入背包的物品時，對每種物品只有兩個選擇：即裝入或 不裝入。不能重復(fù)裝入，也不能只裝入部分的物品i。要求：試設(shè)計一個解決此問題的動態(tài)規(guī)劃算法，并分析算法的計算復(fù)雜 性。二、算法的基本思想該問題具有最優(yōu)子結(jié)構(gòu)特征。標(biāo)準(zhǔn) 0-1背包問題，MaxV表示前i 個物品裝入容量為j的背包中時所能產(chǎn)生的最大價值，結(jié)構(gòu)體 o

2、bjec 表示每一個可裝入物品，其中w表示物品的重量，v表示物品的價值。 如果某物品超過了背包的容量，則該物品一定不能放入背包，問題就 變成了剩余i-1個物品裝入容量為j的背包中所能產(chǎn)生的最大價值； 如果該物品能裝入背包，問題就變成i-1個物品裝入容量為 j-objeci.w 的背包所能產(chǎn)生的最大價值加上物品i的價值objeci.v三、算法的程序?qū)崿F(xiàn)#include using namespace std;int V 200200200;int max(int a,int b)if(a=b) return a;else return b;int KnapSack(int n,int w,int

3、 z,int v,int x,int c,int b) int i,p,q;for(i=0;i=n;i+)Vi00=0;for(p=0;p=c;p+)for (q=0;q=b;q+)V0pq=0;for(i=0;i=n-1;i+)for(p=0;p=c;p+)for(q=0;q=b;q+)if(pwi&q=0;i-)if(VipqVi-1pq)xi=1;p=p-wi; q=q-zi; elsexi=0;COUtVV”選中的物品是:； for(i=0;in;i+) cout xi;coutendl;int r=0;for(i=0;in;i+)(if(xi=1) r+=vi;elser+=0;)r

4、eturn r;)void main()(int mv;int w150;int z150;int v150;int x150;int n,i;int c;int b;/背包最大容量和容積coutvv”請輸入背包的最大容量：endl;cinc;coutvv”請輸入背包的最大容積：endl;cinb;coutvv”輸入物品數(shù)：endl;cinn;coutvv”請分別輸入物品的重量:endl;for(i=0;in;i+)cinwi;coutvv”請分別輸入物品的體積:endl;for(i=0;izi;cout請分別輸入物品的價值:endl;for(i=0;ivi;mv=KnapSack(n,w,z,v,x,c,b);cout最大物品價值為：mvendl;四、算法的復(fù)雜度分析時間復(fù)雜度為O(n)。五、算法運行結(jié)果及分析(截屏)硒“1：八二我隹幽Drbug端占國苜折音包牙筋寸言&二多輸入背包國最大容袒:1OD輸入物品城：%分別輸入他不的里量:5它9請與則輸入牧品的休抵%藕嵋人物品的枷值:g g gI耙微嘉？0Ftbss any key to cantinu.5.輸入數(shù)據(jù)的第一行分別為：背包的容量 c,背包的容積d,物品的個數(shù)n。接下來的n行表示n個物品的重量、體積和價值。輸出為最 大的總價值。六、結(jié)束語包括最優(yōu)子結(jié)構(gòu)性質(zhì)1