算法分析與設(shè)計(jì)背包問(wèn)題實(shí)驗(yàn)報(bào)告

算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告---------背包問(wèn)題實(shí)驗(yàn)名稱(chēng)：算法分析與設(shè)計(jì)—01背包問(wèn)題院系名稱(chēng)：計(jì)算機(jī)學(xué)院專(zhuān)業(yè)：軟件工程班級(jí)：學(xué)號(hào)：學(xué)生姓名：李書(shū)偉指導(dǎo)教師：強(qiáng)贊霞2014年7月一、實(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í)際問(wèn)題。二、實(shí)驗(yàn)內(nèi)容1.問(wèn)題描述：0-1背包問(wèn)題給定n種物品和一個(gè)背包。物品i的重量是wi，體積是bi，其價(jià)值為vi，背包的容量為c，容積為d。問(wèn)應(yīng)如何選擇裝入背包中的物品，使得裝入背包中物品的總價(jià)值最大?在選擇裝入背包的物品時(shí)，對(duì)每種物品只有兩個(gè)選擇：裝入或不裝入，且不能重復(fù)裝入。輸入數(shù)據(jù)的第一行分別為：背包的容量c，背包的容積d，物品的個(gè)數(shù)n。接下來(lái)的n行表示n個(gè)物品的重量、體積和價(jià)值。輸出為最大的總價(jià)值。輸入樣例：20153117995107105輸出樣例192.數(shù)據(jù)輸入：個(gè)人設(shè)定，由鍵盤(pán)輸入。3.要求：1）上述題目任選一做。上機(jī)前，完成程序代碼的編寫(xiě)2）獨(dú)立完成實(shí)驗(yàn)及實(shí)驗(yàn)報(bào)告三、問(wèn)題分析 標(biāo)準(zhǔn)0-1背包問(wèn)題，MaxV表示前i個(gè)物品裝入容量為j的背包中時(shí)所能產(chǎn)生的最大價(jià)值，結(jié)構(gòu)體objec表示每一個(gè)可裝入物品，其中w表示物品的重量，v表示物品的價(jià)值。如果某物品超過(guò)了背包的容量，則該物品一定不能放入背包，問(wèn)題就變成了剩余i-1個(gè)物品裝入容量為j的背包中所能產(chǎn)生的最大價(jià)值；如果該物品能裝入背包，問(wèn)題就變成i-1個(gè)物品裝入容量為j-objec[i].w的背包所能產(chǎn)生的最大價(jià)值加上物品i的價(jià)值objec[i].v.四、算法設(shè)計(jì) 設(shè)背包問(wèn)題中最大價(jià)值為MaxV,背包容量為j時(shí)，可選擇物品為i-n的最大價(jià)值。設(shè)計(jì)結(jié)構(gòu)體表示每一個(gè)物品，更符合面向?qū)ο笏枷?；structobjec{ intw; intv;};五、算法實(shí)現(xiàn)#include<iostream>usingnamespacestd;constintNUM=10000;constintC=10000;intMaxV[C]={0};structobjec{ intw; intv;};int_tmain(intargc,_TCHAR*argv[]){ intn,c;//n為物品種類(lèi)數(shù)，c為背包總?cè)萘?objecob[NUM]; intw[NUM],d[C]; cin>>n>>c; for(inti=1;i<=n;i++) { cin>>ob[i].w>>ob[i].v; } for(inti=1;i<=n;i++) { for(intj=c;j>=ob[i].w;j--) { MaxV[j]=MaxV[j-ob[i].w]+ob[