題目來源：領扣 | LintCode有 i 個物品和一個總容量為 j 的背包. 給定數組 weight 表示每個物品的重量和數組 value 表示每個物品的價值，求最大價值。（物品不能分割）
背包問題II
這道題是一道動态規劃(dp)算法的基礎題，有兩種實作方式，分别是遞歸和遞推（疊代），前者比後者好了解。
解題思路
首先，題目的要求是找出最大價值，是以我們要想，怎麼存放才能讓他的價值最大呢？因為物品具有重量，背包容量也有限，是以我們不能每次都放入最大價值的物品，舉個例子，假設背包容量為 12，現在有三個物品對應價值和重量的關系如下表
物品|品質|價值
A 10 8
B 6 5
C 5 4
顯然我們就要選B和C,然後有人可能就會靈光一閃，那全都選擇成本效益（價值/品質）最大的不就行了（貪心算法），但是題目還有要求“物品不能分割”，是以實際上我們不能使用貪心算法。
我們可以從最普通的思考方式得到一個動态規劃的遞推式子。我們有i個物品，考慮到重量的情況下，按照通常人類的想法就是找出各種組合，然後依次比較這些組合的價值，選最大的那個就行了，是以我們線性周遊i個物品的時候就有兩種選擇，“要”和“不要”，
每個物品都經曆這兩個選擇，最終就是産生全部的組合方式。當輪到第i個物品的時候，我們的最大價值就是這樣一個式子：maxvalue = max(value[i],value[i-1]) （并考慮每次選擇背包能不能裝得下）,意思就是要第i個物品和不要第i個物品那個情況得到的價值最大，因為判斷i個物品我們需要知道i-1個時的最大價值，是以這個式子會一直傳遞到背包滿了或者物品都确認完了，是以可以想到用遞歸來解決這個過程。
遞歸算法實作
我們需要讓程式知道每個物品的資訊，是以需要兩個數組來儲存每個物品對應的資訊（也可用一個結構體數組），分别是value[],weight[]。遞歸程式需要有會變化的參數，物品的價值和重量時不會變的，顯然會變的是物品的數量和背包的剩餘容量，是以可以寫一個函數bag（前i個物品，剩餘背包容量j);
-
找到遞歸出口
上文提到的，背包無剩餘空間或者物品算完了，即（j0||i0)，此時它傳回的最大價值應該是0；
-
遞推關系
這個關系有兩種，比較容易想到的是 maxvalue = max(bag(i-1,j),bag(i-1,j-weight[i])+value[i]) 前一個是“不要”，後一個是“要”；
還有一種情況是 當j!=0但是目前選擇的物品的重量weight[i]比剩下空間j多了，我們就要跳過這個物品，即強制選擇“不要”。
完成這兩部我們就能初步得到遞歸的算法啦！
int bag(int i, int j) //遞歸實作
{
if (i == 0 || j == 0)
return 0;
if (weight[i] > j)
return bag(i-1,j);
else {
int res = max(bag(i - 1, j), bag(i - 1, j - weight[i]) + value[i]);
return res;
}
//max函數可以自己判斷每一種情況下的最大價值（TIPS：對于遞歸程式不能刻意去思考它的過程，主要了解它的方向）
}
然而這個還不能稱為DP,因為這個效率極差，我們發現它計算幾百種情況，難免會出現重複的，重複的節點可能是物品為i,重量為j，是以可以建立一個用來記錄的二維數組maxdata[i][j]，每個i，j都是一種情況，儲存這種情況下的最大價值，這樣效率就能大大提高
int bag(int i, int j) //遞歸實作
{
if (maxdata[i][j] != EOF) //一開始讓每個點都等于EOF（-1），如果不是-1證明這個情況已經算過了，可以直接return
return maxdata[i][j];
if (i == 0 || j == 0)
return 0;
if (weight[i] > j)
return bag(i-1,j);
else {
int res = max(bag(i - 1, j), bag(i - 1, j - weight[i]) + value[i]);
maxdata[i][j] = res; //沒算過就存一下
return res;
}
}
疊代算法
疊代算法和遞歸算法有一個本質的差別，遞歸我們是從i個物品一直找到剩下1個，而疊代算法則恰恰相反，要從一個開始找出最大價值，并逐漸向上得到i個物品能得到的最大價值，而我們要記錄的是前i種物品在各種重量下的最大價值。（這是比較難了解的點）
但是具體的判斷方法仍然是“要”和“不要”的問題。因為是從1個開始，是以我們每輪遞推的關鍵點在于重量，遞推式還是那個樣子max(maxdata[j],max[j-weight[i]]+value[i]);但是我們是根據數組中儲存的前一輪的資料進行判斷的。
然後再來分析一下這個遞推式，假如現在正計算i種物品，maxdata[j]則是i-1種物品對應j重量的最大價值，如果我們“不要”第i個物品，那麼最大價值還是i-1個物品對應的最大價值，如果我們“要”第i個物品，那麼要對應前i-1個物品在容量扣除weight[i]時的最大價值，然後加上value[i]。這兩個數值哪個大就選哪個作為這一輪的最大價值，因為判斷完成後上一輪對應的資料就沒有用了 是以我們新的資料就可以覆寫在對應的位置，即maxdata[j] = max(maxdata[j],maxdata[j-weight[i]]+value[i]);
核心代碼奉上
//遞推（疊代） 滾動數組
int f[100] = { 0 }; //f[j]儲存前一輪各個重量下最大價值
for (int i = 1; i <= n; i++) { //枚舉種類j
for (int j = totalweight; j >= 0; j--){ //算前n種的各個重量下最大價值
int next_w = j - weight[i]; //“要”這個物品的情況下對應的下标
if (next_w < 0) next_w = 0; //防止下标越界
if (weight[i] > j)data
f[j] = f[j]; //超重則最大價值等于前一輪對應容量下的最大價值，直接“不要”
else
f[j] = max(f[j], f[next_w] + value[i]);
if(i==n) break; //最後一個物品隻需要算一個totalweight的就夠了
}
}//最終得到的f[totalweight]就是n個物品用整個背包去裝能得到的最大價值。
了解這個程式，隻要搞懂i = 1 到 i = 2 的過程就能了解全部了。可以随便舉個例子：假設背包容量為 12
編号|物品|品質|價值
1 A 10 8
2 B 6 5
3 C 5 4
-
從第1個A開始，我們發現容量大于等于10的時候最大價值就是8，其他的都是0，此時f[]内的資料全是零，于是大于等于10以後的式子都會是f[j] = max(0,0+8),是以就能得到新的f[]；
f[] = {0 0 0 0 0 0 0 0 0 0 8 8 8 ……}
-
然後在看第二個物品B,
在總容量為12時，有f[12] = max(f[12],f[12-6]+5) f[12]從前一輪得出等于8，f[6] = 0, 是以顯然在這個容量的限制下，我們會選擇“不要”。
以此類推，我們可以發現直到 5<j<10 我們才會選擇"要”，是以可以得到這一輪的f[] = {0 0 0 0 0 0 6 6 6 6 8 8 8……}
-
如果還沒了解就，繼續看下第三個物品C
跟前一輪完全相同的想法，當j=12的時候，f[12] = max(f[12],f[12-5]+4) 我們發現 f[12] = 8 < f[7]+5 = 11; 是以我們選擇“要”
因為這是最後一個了是以繼續往下算已經沒用了，我們已經得到3個物品，12容量下的最大價值則為 11 ；
到這裡疊代算法就算講解完了！！
疊代算法的流程圖
閑話
第一次寫這種部落格，感覺還挺有趣的，最重要的是還能讓自己複習學過的知識，本篇内容是按自己的了解寫的，可能存在邏輯錯誤或者漏洞，如果發現問題還請評論指教。
動态規劃的學習可以參考mooc上郭偉的《算法與程式設計》，最簡單的dp問題有 數字金字塔 等。動态規劃太靈活了，沒有固定的模闆，要根據問題具體分析
完整代碼參考我的GitHub