動(dòng)態(tài)規(guī)劃解決0

1、算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告2015-2016年第2學(xué)期實(shí)驗(yàn)班級(jí)：學(xué)生姓名：學(xué) 號(hào)：指導(dǎo)老師：信息工程學(xué)院實(shí)驗(yàn)項(xiàng)目名稱：動(dòng)態(tài)規(guī)劃解決0-1背包問題實(shí)驗(yàn)日期：2016年4月27日一、 實(shí)驗(yàn)類型：驗(yàn)證性口設(shè)計(jì)性二、實(shí)驗(yàn)?zāi)康?、明確0-1背包問題的概念2、利用動(dòng)態(tài)規(guī)劃解決0-1背包問題三、實(shí)驗(yàn)內(nèi)容及要求0-1背包問題(knapsack problem)，某商店有n個(gè)物品，第i個(gè)物品價(jià)值為vi，重量(或 稱權(quán)值)為wi，其中vi和wi為非負(fù)數(shù)，背包的容量為W，W為一非負(fù)數(shù)。目標(biāo)是如何 選擇裝入背包的物品，使裝入背包的物品總價(jià)值最大，所選商品的一個(gè)可行解即所選 商品的序列如何？背包問題與0-1背包問題的不同點(diǎn)

2、在于，在選擇物品裝入背包時(shí)， 可以只選擇物品的一部分，而不一定要選擇物品的全部?？蓪⑦@個(gè)問題形式描述如下: max V v.x；X 叫町 xt G 再1? 約束條件為： lfM四、實(shí)驗(yàn)步驟#include #include#includeint min(int w,int c)( int temp;if (wc) temp=w;else temp=c;return temp;void knapsack(int v,int w,int c,int n,int*m) /求最優(yōu)值int jmax=min(wn-1,c);for(int j=0;j=jmax;j+)mnj=0;for(int jj=w

3、n;jj1;i-) 遞歸部分jmax=min(wi-1,c);for(int j=0;j=jmax;j+)mij=mi+1j;for(int jj=wi;jj=w1)m1c=max(m1c,m c-w1+v1);cout最優(yōu)值：m1cendl;coutendl;1. _ f f “ “ “ “ “ “ “ “ “ “ “ “ “ “ “ “ “ “ “ “ “ “ “ “ “ “ “ “ “ “ “ “ “ “ “ “ “ “ “ “ “ “ “ 11 一 一 11coutvv*vvendi;int traceback(int *m,int w,int c,int n,int x) /回代，求

4、最優(yōu)解cout得到的一組最優(yōu)解如下:vvendl;if(mi c=mi+l c) xi=O;else xi=l;c-=wi;xn=(mn c)?l :0;for(int y=l;yv=n;y+) coutsetw(5)xy;coutendl;return xn;void main() int n,c;int *m;coutiW輸入物品個(gè)數(shù)和重量上限:”;cinnc;int *v=new intn+l;cout請(qǐng)輸入價(jià)值(vi):endl;for(int i=l;iv=n;i+)cinvi;int *w=new intn+l;cout請(qǐng)輸入重量(wi):endl;for(int j=1 ；j v

5、=n;j+)cinwj;int *x=new intn+l;m=new int*n+l; /動(dòng)態(tài)的分配二維數(shù)組for(int p=0;pvn+l;p+) mp=new intc+l;knapsack(v,w,c,n,m);traceback(m,w,c,n,x);五、實(shí)驗(yàn)結(jié)果1、實(shí)驗(yàn)圖形I C:Wi nd o wssystem32Debug13213. exeL_lJ=LlBSl請(qǐng)輸入物品個(gè)數(shù)和重量上限：4 2。-請(qǐng)輸入價(jià)值（vi）: 10 13 14 15 請(qǐng)輸入.重量 5 6 3 7 最優(yōu)值：42三:t=t=t=t=t=t=t=t=t=t=t=t=t=t=t=t=t=+=+=+=t=t=t

6、=t=t=t=t=t=t=t=t=t=t=t=t=t=+=+=+=t=t=t=t： 得到的一組最優(yōu)解如下： 0111Press :any key to continue2、結(jié)果分析輸入物品個(gè)數(shù)和重量上限為4、20,輸入物品的價(jià)值分別為10、13、14、15,重量分別為5、6、3、7，得到最優(yōu)值為42，得到一組最優(yōu)解為0 111。3、實(shí)驗(yàn)總結(jié)本次的實(shí)驗(yàn)主要是讓我們初步明確0-1背包問題的概念，并且能夠利用動(dòng)態(tài) 規(guī)劃解決0-1背包問題，這次試驗(yàn)首先，我們要設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法，我們通 常先找出最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征，然后遞歸地定義最優(yōu)解的值，再然 后以自下而上的方式計(jì)算出最優(yōu)值，最后根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一 個(gè)最優(yōu)