0-1背包問題說的是，給定背包容量W，壹系列物品{weiht,value}，每個物品只能取壹件，獲取最大值。
采用動態規劃求解，動態規劃的壹般規律都是，
在什麽什麽前i個狀態下的最大值或者最小值的前提下，然後再把i的狀態的值求出來。
這裏我們定義壹個函數，表示狀態。
m(1,2,3,4..i)(w)表示有1號,2號,3號,4號....i號物品，背包容量為w的時能夠取得的最大值。舉例說明，
假設1，2,3,4,5號物品，它們的重量分別是2,2,6,5,4，用weight(i)表示，它們的價值分別是6,3,5,4,6用value(i)表示
m(1)(1)表只有1號物品，背包容量為1的時候，最大值。顯然，
m(1)(1) = 0，因為背包容量小於2，所以最大值為0。
m(1)(2) = 6, 此時背包容量等於2，裝下1號物品，最大值為6，接下來
m(1)(3) = 6,m(1)(4) = 6，...m(1)(..) = 6,因為只有壹件物品，最大為6。
m(1,2)(1),m(1,2)(2),m(1,2)(3)表示有物品1號，2號，背包容量分別為1,2,3的時候最大值。
最大值和物品的數量相關，也和背包容量相關。
這裏必須強調壹下，m(1,2,3,...i)(w) 表示有1,2,3,4....i，這麽多物品可選，未必全部裝進去的情況下(受限於w)的最大值。
接下來討論在1,2,3.....i物品的最大值。對於第i件物品，背包容量為W，有兩種情況，
1）不把第i件物品裝進背包，那麽此時，只有1,2,3,4,,,,i-1件物品，背包的最大值是m(1,2,3,4,5....i-1)(W)。此時，不管W多麽大，即使和宇宙壹樣大，背包裏的價值之和1,2,3,4,5..i-1這些物品相關。
2）把第i件物品裝進去。既然把i件物品裝進背包，那麽1,2,3,4.....i-1物品只能占用 W-weight(i) 這麽多重量了。這個時候，
之前的1,2,3,4......i-1物品在背包容量為（W-weight(i)）下的最大值為m(1,2,3.......i-1)[ W - weight(i) ]。
此時背包的最大值就是 第i件物品的價值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)?]。?
這裏有人會說，前1,2,3,4.....i-1件物品在W-weight或者W的容量下怎麽求啊。
這裏就說到動態規劃的點上。動態規劃有點數學歸納法的感覺，不過是從後向前推到，要求解i，先求解i-1,；要求解i-1，先求解i-2，這樣壹步壹步到2,1。因此需要給定初始狀態。我們壹直用1,2,3,4.....i-1表示前i-1件物品，太麻煩，直接用i-1表示好了。
m(1,2,3,4....i-1)(w) ====(書寫方便)>m(i-1)(w)，這樣上面的狀態轉移方程就出來。
m(i)(W) = max( m(i-1)(W- weight(i))+value(i), m(i-1)(w) )
這樣，狀態的轉移方程就出來。這裏不得不說下，網上的其他教程這壹點上說的不夠仔細，上來就搞壹個
f[i-1][j] = max(f[i-1][j-w(i)]+value[i],f[i-1][j])。誰看的懂啊。
這裏我們針對上面的數值給出具體的求解過程。首先給出物品的函數值。
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,
那麽最大值函數
m(1)(1) = 0；物品重量為2.
m(1)(2) = 6, 物品恰好放入背包。
m(1)(3) = 6，m(1)(4) = 6...，只有1號物品，最大值只能為6。現在考慮有第2件物品的情況，現在有兩件物品，m函數表示為
m(1,2)(w)。
根據之前所說 1），如果不把2號物品放入，那問題回到只有1號物品的情況
那麽
m(1)(1) = 0,1號物品放不進，
m(1)(2) = 6, 1號物品放進背包。
m(1)(3) = 6, 1號物品放進容量為3的背包
m(1)(4) = 6, 1號物品放進容量為4的背包。
根據之前所說2），把2號物品放入，此時需要 1號物品在背包容量w減去2號物品的容量weight(2),即 w-2的問題。
m(1)(1 - 2) = 0,顯然，此時背包總容量為1，還有減去2號物品的容量2，1-2=-1 ，顯然放不進去。
m(1)(2 - 2) = 0,顯然，背包的容量減去2號物品的容量後，沒有剩余，就是說只能放2號物品，此時背包的最大值
m(1,2)(2)? =? max(m(1,2)(2-2)+value(2),? m(1)(2))= max(0+3,6) = 6。就是說，在有1,2兩件物品，背包容量為2的情況下，最大值為6。
繼續考慮背包容量為3，第壹種情況的已經討論。現在討論第二種情況，把2號物品放入背包，就要剩下w-2的容量給1號了。
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。
繼續考慮背包容量為4，同理，第壹種情況討論，只討論第二種情況，把2號物品放入背包，就要剩下w-2的容量給1號了。
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;
此時m(1,2)(4) = 9;之後，背包容量為5，6,7，。的時候，1,2物品都放進去，最大值不再改變，都是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;
剩下的推導都是如此，根據背包容量壹步壹步的推導即可。