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

算法設(shè)計(jì)與分析實(shí)驗(yàn)報(bào)告---------背包問題實(shí)驗(yàn)名稱：算法分析與設(shè)計(jì)—01背包問題院系名稱：計(jì)算機(jī)學(xué)院專業(yè)：軟件工程班級(jí)：學(xué)號(hào)：學(xué)生姓名：李書偉指導(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í)際問題。二、實(shí)驗(yàn)內(nèi)容1.問題描述：0-1背包問題給定n種物品和一個(gè)背包。物品i的重量是wi，體積是bi，其價(jià)值為vi，背包的容量為c，容積為d。問應(yīng)如何選擇裝入背包中的物品，使得裝入背包中物品的總價(jià)值最大?在選擇裝入背包的物品時(shí)，對(duì)每種物品只有兩個(gè)選擇：裝入或不裝入，且不能重復(fù)裝入。輸入數(shù)據(jù)的第一行分別為：背包的容量c，背包的容積d，物品的個(gè)數(shù)n。接下來的n行表示n個(gè)物品的重量、體積和價(jià)值。輸出為最大的總價(jià)值。輸入樣例：20153117995107105輸出樣例192.數(shù)據(jù)輸入：個(gè)人設(shè)定，由鍵盤輸入。3.要求：1）上述題目任選一做。上機(jī)前，完成程序代碼的編寫2）獨(dú)立完成實(shí)驗(yàn)及實(shí)驗(yàn)報(bào)告三、問題分析 標(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-objec[i].w的背包所能產(chǎn)生的最大價(jià)值加上物品i的價(jià)值objec[i].v.四、算法設(shè)計(jì) 設(shè)背包問題中最大價(jià)值為MaxV,背包容量為j時(shí)，可選擇物品為i-n的最大價(jià)值。設(shè)計(jì)結(jié)構(gòu)體表示每一個(gè)物品，更符合面向?qū)ο笏枷耄籹tructobjec{ 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為物品種類數(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[