算法設(shè)計(jì)背包問題

1、精品文檔算法實(shí)驗(yàn)報(bào)告- 背包問題實(shí)驗(yàn)?zāi)康?掌握動(dòng)態(tài)規(guī)劃算法的基本思想，包括最優(yōu)子結(jié)構(gòu)性質(zhì)和基于表格的最優(yōu) 值計(jì)算方法。2熟練掌握分階段的和遞推的最優(yōu)子結(jié)構(gòu)分析方法。3學(xué)會(huì)利用動(dòng)態(tài)規(guī)劃算法解決實(shí)際問題。問題描述：給定n種物品和一個(gè)背包。物品i的重量是wi，體積是bi，其價(jià)值為vi , 背包的容量為c，容積為d。問應(yīng)如何選擇裝入背包中的物品，使得裝入背包中 物品的總價(jià)值最大 ? 在選擇裝入背包的物品時(shí)， 對每種物品只有兩個(gè)選擇： 裝入 或不裝入，且不能重復(fù)裝入。輸入數(shù)據(jù)的第一行分別為：背包的容量c,背包的容積d，物品的個(gè)數(shù)n。接下來的n行表示n個(gè)物品的重量、體積和價(jià)值。輸出 為最大的總價(jià)值。問題分

2、析:標(biāo)準(zhǔn)0-1背包問題，MaxV表示前i個(gè)物品裝入容量為j的背包中時(shí)所能產(chǎn)生的最大價(jià)值， 結(jié)構(gòu)體 objec 表示每一個(gè)可裝入物品，其中 w 表示物品的重量， v 表示物品的價(jià)值。如果某 物品超過了背包的容量， 則該物品一定不能放入背包， 問題就變成了剩余 i-1 個(gè)物品裝入容 量為 j 的背包中所能產(chǎn)生的最大價(jià)值； 如果該物品能裝入背包， 問題就變成 i-1 個(gè)物品裝入 容量為 j-objeci.w 的背包所能產(chǎn)生的最大價(jià)值加上物品 i 的價(jià)值 objeci.v.復(fù)雜性分析時(shí)間復(fù)雜度，最好情況下為 0，最壞情況下為： (abc)源程序#include #include #include#in

3、clude #includeint V 200200200;int max(int a,int b)精品文檔if(a=b)return a;elsereturn b;int KnapSack(int n,int w,int 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-w

4、i; q=q-zi;else xi=0;cout 選中的物品是 :; for(i=0;in;i+) cout xi; coutendl;int r=0; for(i=0;in;i+)if(xi=1) r+=vi;else r+=0;2歡迎。下載精品文檔return r;void mai n()int mv;int w150;int z150;in t v150;int x150;int n,i;in t c;i nt b;背包最大容量和容積coutvv請輸入背包的最大容量: c;coutvv請輸入背包的最大容積：vvendl; cin b;coutvv輸入物品數(shù):n;coutvv請分別輸入物品的重量:vvendl; for(i=0;iv n;i+)ci n wi;coutvv請分別輸入物品的體積:vvendl; for(i=0;iv n;i+)cin zi;coutvv請分別輸入物品的價(jià)值:vvendl; for(i=0;iv n;i+)cin vi;mv=K napSack( n, w,z,v,x,c,b);coutvv最大物品價(jià)值