首先說下動态規劃，動态規劃這東西就和遞歸一樣，隻能找局部關系，若想全部列出來，是很難的，比如漢諾塔。你可以說先把除最後一層的其他所有層都移動到2，再把最後一層移動到3，最後再把其餘的從2移動到3，這是一個直覺的關系，但是想列舉出來是很難的，也許當層數n=3時還可以模拟下，再大一些就不可能了，是以，諸如遞歸，動态規劃之類的，不能細想，隻能找局部關系。
1.漢諾塔圖檔
（引至杭電課件:DP最關鍵的就是狀态，在DP時用到的數組時，也就是存儲的每個狀态的最優值，也就是記憶化搜尋）
要了解背包，首先得清楚動态規劃：
動态規劃算法可分解成從先到後的4個步驟：
1. 描述一個最優解的結構；
2. 遞歸地定義最優解的值；
3. 以“自底向上”的方式計算最優解的值；
4. 從已計算的資訊中建構出最優解的路徑。
其中步驟1~3是動态規劃求解問題的基礎。如果題目隻要求最優解的值，則步驟4可以省略。
背包的基本模型就是給你一個容量為V的背包
在一定的限制條件下放進最多(最少?)價值的東西
目前狀态→ 以前狀态
看了dd大牛的《背包九講》(點選下載下傳)，迷糊中帶着一絲清醒，這裡我也總結下01背包，完全背包，多重背包這三者的使用和差別，部分會引用dd大牛的《背包九講》，如果有錯，歡迎指出。
(www.wutianqi.com留言即可)
首先我們把三種情況放在一起來看：
01背包（ZeroOnePack）: 有N件物品和一個容量為V的背包。（每種物品均隻有一件）第i件物品的費用是c[i]，價值是w[i]。求解将哪些物品裝入背包可使價值總和最大。
完全背包(CompletePack): 有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的費用是c[i]，價值是w[i]。求解将哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。
多重背包(MultiplePack): 有N種物品和一個容量為V的背包。第i種物品最多有n[i]件可用，每件費用是c[i]，價值是w[i]。求解将哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。
比較三個題目，會發現不同點在于每種背包的數量，01背包是每種隻有一件，完全背包是每種無限件，而多重背包是每種有限件。
——————————————————————————————————————————————————————————–
先來分析01背包：
01背包（ZeroOnePack）: 有N件物品和一個容量為V的背包。（每種物品均隻有一件）第i件物品的費用是c[i]，價值是w[i]。求解将哪些物品裝入背包可使價值總和最大。
這是最基礎的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。
用子問題定義狀态：即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀态轉移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
把這個過程了解下：在前i件物品放進容量v的背包時，
它有兩種情況：
第一種是第i件不放進去，這時所得價值為:f[i-1][v]
第二種是第i件放進去，這時所得價值為：f[i-1][v-c[i]]+w[i]
（第二種是什麼意思？就是如果第i件放進去，那麼在容量v-c[i]裡就要放進前i-1件物品）
最後比較第一種與第二種所得價值的大小，哪種相對大，f[i][v]的值就是哪種。
（這是基礎，要了解！）
這裡是用二位數組存儲的，可以把空間優化，用一位數組存儲。
用f[0..v]表示，f[v]表示把前i件物品放入容量為v的背包裡得到的價值。把i從1~n(n件)循環後，最後f[v]表示所求最大值。
*這裡f[v]就相當于二位數組的f[i][v]。那麼，如何得到f[i-1][v]和f[i-1][v-c[i]]+w[i]？（重點！思考）
首先要知道，我們是通過i從1到n的循環來依次表示前i件物品存入的狀态。即：for i=1..N
現在思考如何能在是f[v]表示目前狀态是容量為v的背包所得價值，而又使f[v]和f[v-c[i]]+w[i]标簽前一狀态的價值？
逆序！
這就是關鍵！
| 1 2 3 | |
分析上面的代碼：當内循環是逆序時，就可以保證後一個f[v]和f[v-c[i]]+w[i]是前一狀态的！
這裡給大家一組測試資料：
測試資料：
10,3
3,4
4,5
5,6
這個圖表畫得很好，借此來分析：
C[v]從物品i=1開始，循環到物品3，期間，每次逆序得到容量v在前i件物品時可以得到的最大值。（請在草稿紙上自己畫一畫）
這裡以一道題目來具體看看：
題目：http://acm.hdu.edu.cn/showproblem.php?pid=2602
代碼在這裡：http://www.wutianqi.com/?p=533
分析：
具體根據上面的解釋以及我給出的代碼分析。這題很基礎，看懂上面的知識應該就會做了。
——————————————————————————————————————————————————————————–
完全背包：
完全背包(CompletePack): 有N種物品和一個容量為V的背包，每種物品都有無限件可用。第i種物品的費用是c[i]，價值是w[i]。求解将哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。
完全背包按其思路仍然可以用一個二維數組來寫出：
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}
同樣可以轉換成一維數組來表示：
僞代碼如下：
| 1 2 3 | |
順序！
想必大家看出了和01背包的差別，這裡的内循環是順序的，而01背包是逆序的。
現在關鍵的是考慮：為何完全背包可以這麼寫？
在次我們先來回憶下，01背包逆序的原因？是為了是max中的兩項是前一狀态值，這就對了。
那麼這裡，我們順序寫，這裡的max中的兩項當然就是目前狀态的值了，為何？
因為每種背包都是無限的。當我們把i從1到N循環時，f[v]表示容量為v在前i種背包時所得的價值，這裡我們要添加的不是前一個背包，而是目前背包。是以我們要考慮的當然是目前狀态。
這裡同樣給大家一道題目：
題目：http://acm.hdu.edu.cn/showproblem.php?pid=1114
代碼：http://www.wutianqi.com/?p=535
（分析代碼也是學習算法的一種途徑，有時并不一定要看算法分析，結合題目反而更容易了解。）
——————————————————————————————————————————————————————————–
多重背包
多重背包(MultiplePack): 有N種物品和一個容量為V的背包。第i種物品最多有n[i]件可用，每件費用是c[i]，價值是w[i]。求解将哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。
這題目和完全背包問題很類似。基本的方程隻需将完全背包問題的方程略微一改即可，因為對于第i種物品有n[i]+1種政策：取0件，取1件……取n[i]件。令f[i][v]表示前i種物品恰放入一個容量為v的背包的最大權值，則有狀态轉移方程：
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}
這裡同樣轉換為01背包：
普通的轉換對于數量較多時，則可能會逾時，可以轉換成二進制（暫時不了解，是以先不講）
對于普通的。就是多了一個中間的循環，把j=0~bag[i]，表示把第i中背包從取0件枚舉到取bag[i]件。
給出一個例題：
題目：http://acm.hdu.edu.cn/showproblem.php?pid=2191
代碼：http://www.wutianqi.com/?p=537
因為限于個人的能力，我隻能講出個大概，請大家具體還是好好看看dd大牛的《背包九講》。
原文下載下傳位址：（Word版）
http://download.csdn.net/source/2587577