所謂九講，也就是：

0/1背包

0/1背包降維

完全背包

多重背包(二進制優(yōu)化)

混合背包

二維費用背包

分組背包

有依賴的背包

背包的方案總數(shù)\背包的具體方案路徑

0/1背包：

[問題描述]（經(jīng)典）
有一個吝嗇的地主，不愿意給工人付工錢，就從家里的物品中取出N個，對工人說， 你可以從這些物品中任意挑選，只要你的口袋裝得下。 現(xiàn)在已知物品的總數(shù)量N，和工人的口袋大小M，及每種物品所占的空間wi，物品的價值vi。求出該背包能裝載的最大價值。（物品不可以分，不考慮物品間的縫隙） 輸入：

2    8
8    6
3    4 
5    4
3    3

輸出：

16

有人說貪心 不就對了，是啊，當(dāng)然不對。 貪心：先選單位空間能獲得價值更大者

2:8
3:4
3:3
15

正確選擇：

2 8
3 4
5 4
16

懂？ 當(dāng)然用深搜的dalao我就不說了，這明顯是01背包嘛。 第一步：狀態(tài)設(shè)想

總問題：N個物品，占用M個空間時所能獲得的最大價值。

子問題：f[i,j] ：前i個物品占用j個空間時能獲得的最大價值。（背包慣用定義方式）

第二步：初步規(guī)劃動規(guī)方程

?從某個中間狀態(tài)思考來源

F[i][j]=……….設(shè)前面的任何決策都有答案了，當(dāng)前決策？（來源法）

因為只有選和不選兩種方案，所以f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]);(若不選，及前i-1個物品占j個空間的最大價值，f[i-1][j]，

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 若選，及前i-1個物品占j-w[i]個空間的最大價值，f[i-1][j-w[i]]）

第三步：打表? 驗證、確定動規(guī)方程

轉(zhuǎn)載于:https://www.cnblogs.com/mzyczly/p/11174542.html

總結(jié)

以上是生活随笔為你收集整理的浅说——九讲背包之01背包的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。