0019算法筆記——【動態(tài)規(guī)劃】0-1背包問題

《0019算法筆記——【動態(tài)規(guī)劃】0-1背包問題》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、0019算法筆記——【動態(tài)規(guī)劃】0-1背包問題?????1、問題描述：????給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為C。問:應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?????形式化描述：給定c>0,wi>0,vi>0,1≤i≤n.要求找一n元向量(x1,x2,…,xn,),xi∈{0,1},?∑wixi≤c,且∑vixi達最大.即一個特殊的整數(shù)規(guī)劃問題。???????2、最優(yōu)性原理：????設(shè)(y1,y2,…,yn)是(3.4.1)的一個最優(yōu)解.則(y2,…,yn)是下面相應(yīng)子問題的一個最優(yōu)解:????證明:使用反

2、證法。若不然,設(shè)(z2,z3,…,zn)是上述子問題的一個最優(yōu)解,而(y2,y3,…,yn)不是它的最優(yōu)解。顯然有???????????????????????????????????∑vizi?>∑viyi??(i=2,…,n)????且??????????????????????????w1y1+∑wizi<=c????因此??????????????????????v1y1+∑vizi?(i=2,…,n)>∑viyi,(i=1,…,n)?????說明(y1,z2,z3,…,zn)是(3.4.1)0-1背包問題的一個更優(yōu)解,導(dǎo)出(y1,y2,…,yn)不是

3、背包問題的最優(yōu)解,矛盾。???????3、遞推關(guān)系：????設(shè)所給0-1背包問題的子問題?????????的最優(yōu)值為m(i，j)，即m(i，j)是背包容量為j，可選擇物品為i，i+1，…，n時0-1背包問題的最優(yōu)值。由0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計算m(i，j)的遞歸式:????注:(3.4.3)式此時背包容量為j，可選擇物品為i。此時在對xi作出決策之后,問題處于兩種狀態(tài)之一:???(1)背包剩余容量是j,沒產(chǎn)生任何效益；???(2)剩余容量j-wi,效益值增長了vi?；?????算法具體代碼如下：[cpp]?viewplain?copy1.//

4、3d10-1?動態(tài)規(guī)劃?背包問題??2.#include?"stdafx.h"??3.#include????4.using?namespace?std;???5.??6.const?int?N?=?4;??7.??8.void?Knapsack(int?v[],int?w[],int?c,int?n,int?m[][10]);??9.void?Traceback(int?m[][10],int?w[],int?c,int?n,int?x[]);??10.??11.int?main()??12.{??13.????int?c=8;??14.

5、????int?v[]={0,2,1,4,3},w[]={0,1,4,2,3};//下標從1開始??15.????int?x[N+1];??16.????int?m[10][10];??17.??18.????cout<<"待裝物品重量分別為："<

6、int?i=1;?i<=N;?i++)??27.????{??28.????????cout<

7、?2.????????if(x[i]==1)??3.????????{??4.????????????cout<

8、=jMax;j++)??16.????