網(wǎng)上好多關(guān)于背包問題的解釋，自己也看了贷洲，感覺解釋的不容易通俗易懂，所以自己來寫一個(gè)非常容易懂得晋柱。

0-1背包問題說的是优构，給定背包容量W，一系列物品{weiht,value}雁竞，每個(gè)物品只能取一件钦椭，獲取最大值。

采用動(dòng)態(tài)規(guī)劃求解碑诉，動(dòng)態(tài)規(guī)劃的一般規(guī)律都是彪腔，

在什么什么前i個(gè)狀態(tài)下的最大值或者最小值的前提下，然后再把i的狀態(tài)的值求出來进栽。

這里我們定義一個(gè)函數(shù)德挣，表示狀態(tài)。

m(1,2,3,4..i)(w)表示有1號(hào),2號(hào),3號(hào),4號(hào)....i號(hào)物品快毛，背包容量為w的時(shí)能夠取得的最大值格嗅。舉例說明番挺，

假設(shè)1，2,3,4,5號(hào)物品吗浩，它們的重量分別是2,2,6,5,4，用weight(i)表示没隘，它們的價(jià)值分別是6,3,5,4,6用value(i)表示

m(1)(1)表只有1號(hào)物品懂扼，背包容量為1的時(shí)候，最大值右蒲。顯然阀湿，

m(1)(1) = 0，因?yàn)楸嘲萘啃∮?瑰妄，所以最大值為0陷嘴。

m(1)(2) = 6, 此時(shí)背包容量等于2，裝下1號(hào)物品间坐，最大值為6灾挨，接下來

m(1)(3) = 6,m(1)(4) = 6，...m(1)(..) = 6,因?yàn)橹挥幸患锲分袼危畲鬄?劳澄。

m(1,2)(1),m(1,2)(2),m(1,2)(3)表示有物品1號(hào)，2號(hào)蜈七，背包容量分別為1,2,3的時(shí)候最大值秒拔。

最大值和物品的數(shù)量相關(guān)，也和背包容量相關(guān)飒硅。

這里必須強(qiáng)調(diào)一下砂缩，m(1,2,3,...i)(w) 表示有1,2,3,4....i，這么多物品可選三娩，未必全部裝進(jìn)去的情況下(受限于w)的最大值庵芭。

接下來討論在1,2,3.....i物品的最大值。對(duì)于第i件物品雀监，背包容量為W喳挑，有兩種情況，

1）不把第i件物品裝進(jìn)背包滔悉，那么此時(shí)伊诵，只有1,2,3,4,,,,i-1件物品，背包的最大值是m(1,2,3,4,5....i-1)(W)回官。此時(shí)曹宴，不管W多么大，即使和宇宙一樣大歉提，背包里的價(jià)值之和1,2,3,4,5..i-1這些物品相關(guān)笛坦。

2）把第i件物品裝進(jìn)去区转。既然把i件物品裝進(jìn)背包，那么1,2,3,4.....i-1物品只能占用 W-weight(i) 這么多重量了版扩。這個(gè)時(shí)候废离，

之前的1,2,3,4......i-1物品在背包容量為（W-weight(i)）下的最大值為m(1,2,3.......i-1)[ W - weight(i) ]。

此時(shí)背包的最大值就是 第i件物品的價(jià)值value(i)加上

前1,2,3,4....i-1件物品在背包容量為（W-weight(i) 下的最大值m(1,2,3.......i-1)[ W - weight(i) ]

m（1,2,3,4.......i-1,i)(W)= m(1,2,3.......i-1)[ W - weight(i) ] +? ?value(i) ;

然后我們比較一下礁芦，情況1）2）的最大值就可以了 即

m(1,2,3,4....i-1,i)(W) = max[? m(1,2,3.......i-1)[ W - weight(i) ] +? ?value(i) ,?m(1,2,3,4,5....i-1)(W)?]蜻韭。?

這里有人會(huì)說，前1,2,3,4.....i-1件物品在W-weight或者W的容量下怎么求啊柿扣。

這里就說到動(dòng)態(tài)規(guī)劃的點(diǎn)上肖方。動(dòng)態(tài)規(guī)劃有點(diǎn)數(shù)學(xué)歸納法的感覺，不過是從后向前推到未状，要求解i俯画，先求解i-1,；要求解i-1司草，先求解i-2艰垂，這樣一步一步到2,1。因此需要給定初始狀態(tài)埋虹。我們一直用1,2,3,4.....i-1表示前i-1件物品材泄，太麻煩，直接用i-1表示好了吨岭。

m(1,2,3,4....i-1)(w) ====(書寫方便)>m(i-1)(w)拉宗，這樣上面的狀態(tài)轉(zhuǎn)移方程就出來。

m(i)(W) = max( m(i-1)(W- weight(i))+value(i), m(i-1)(w) )

這樣辣辫，狀態(tài)的轉(zhuǎn)移方程就出來旦事。這里不得不說下，網(wǎng)上的其他教程這一點(diǎn)上說的不夠仔細(xì)急灭，上來就搞一個(gè)

f[i-1][j] = max(f[i-1][j-w(i)]+value[i],f[i-1][j])姐浮。誰看的懂啊。

這里我們針對(duì)上面的數(shù)值給出具體的求解過程葬馋。首先給出物品的函數(shù)值卖鲤。

weight(1) = 2,value(1) =?6,

weight(2) = 2,value(2) = 3,

weight(3) = 6,value(3) = 5,

weight(4) = 5,value(4) = 4,

weight(5) = 4,value(5) =?6,

那么最大值函數(shù)

m(1)(1) = 0；物品重量為2.

m(1)(2) = 6, 物品恰好放入背包畴嘶。

m(1)(3) = 6蛋逾，m(1)(4) = 6...，只有1號(hào)物品窗悯，最大值只能為6∏唬現(xiàn)在考慮有第2件物品的情況，現(xiàn)在有兩件物品蒋院，m函數(shù)表示為

m(1,2)(w)亏钩。

根據(jù)之前所說 1）莲绰，如果不把2號(hào)物品放入，那問題回到只有1號(hào)物品的情況

那么

m(1)(1) = 0,1號(hào)物品放不進(jìn)姑丑，

m(1)(2) = 6, 1號(hào)物品放進(jìn)背包蛤签。

m(1)(3) = 6, 1號(hào)物品放進(jìn)容量為3的背包

m(1)(4) = 6, 1號(hào)物品放進(jìn)容量為4的背包。

根據(jù)之前所說2）栅哀，把2號(hào)物品放入震肮，此時(shí)需要 1號(hào)物品在背包容量w減去2號(hào)物品的容量weight(2),即 w-2的問題。

m(1)(1 - 2) = 0,顯然昌屉，此時(shí)背包總?cè)萘繛?钙蒙，還有減去2號(hào)物品的容量2茵瀑，1-2=-1 间驮，顯然放不進(jìn)去。

m(1)(2 - 2) = 0,顯然马昨，背包的容量減去2號(hào)物品的容量后竞帽，沒有剩余，就是說只能放2號(hào)物品鸿捧，此時(shí)背包的最大值

m(1,2)(2)? =? max(m(1,2)(2-2)+value(2),? m(1)(2))= max(0+3,6) = 6屹篓。就是說，在有1,2兩件物品匙奴，背包容量為2的情況下堆巧，最大值為6。

繼續(xù)考慮背包容量為3泼菌，第一種情況的已經(jīng)討論〉簦現(xiàn)在討論第二種情況，把2號(hào)物品放入背包哗伯，就要剩下w-2的容量給1號(hào)了荒揣。

m(1,2)(w-2)= m(1,2)(3-2)=m(1,2)(1)? = 0, value(2) = 3因此，

m(1,2)(3) = max[?m(1,2)(3-2)+value(2),m(1)(3)]?= max(0+3,6) = 6焊刹。

繼續(xù)考慮背包容量為4系任，同理，第一種情況討論虐块，只討論第二種情況俩滥，把2號(hào)物品放入背包，就要剩下w-2的容量給1號(hào)了贺奠。

m(1,2)(4-2)=m(1,2)(2)=6,value(2) = 3

m(1,2)(4) = max[ m(1,2)(4-2)+value(2),m(1)(4)]=max[m(1,2)(2)+value(2),m(1)(4)] = max(6+3,6) = 9;

此時(shí)m(1,2)(4) = 9;之后举农，背包容量為5，6,7敞嗡，颁糟。的時(shí)候航背，1,2物品都放進(jìn)去，最大值不再改變棱貌，都是9

m(1,2)(5) = 9玖媚，m(1,2)(6) = 9，m(1,2)(7) = 9婚脱，m(1,2)(8) = 9

同理今魔，weight(3) = 6,value(3)=5

m(1,2,3)(1) = max[ m(1,2,3)(1-6)+value(3),m(1,2)(1)?] = 0

m(1,2,3)(2) = max[ m(1,2,3)(2-6)+value(3),m(1,2)(2)? ] =6

m(1,2,3)(3) = max[ m(1,2,3)(3-6)+value(3),m(1,2)(3)? ] =6

m(1,2,3)(4) = max[ m(1,2,3)(4-6)+value(3),m(1,2)(4)? ] =9

m(1,2,3)(5) = max[ m(1,2,3)(5-6)+value(3),m(1,2)(5)? ] =9

m(1,2,3)(6) = max[ m(1,2,3)(6-6)+value(3),m(1,2)(6)? ] = 9

m(1,2,3)(7) = max[ m(1,2,3)(7-6)+value(3),m(1,2)(7)? ] = max[m(1,2,3)(1)+5,9] = max[0+5,9]=9

m(1,2,3)(8) = max[ m(1,2,3)(8-6)+value(3),m(1,2)(8)? ] = max[m(1,2,3)(2)+5,9] = max[6+5,9]=11;

剩下的推導(dǎo)都是如此，根據(jù)背包容量一步一步的推導(dǎo)即可障贸。