本文主要總結我對背包問題學習的心得，主要是把我以前在印象筆記中的內容搬了過來。
先給出常見的背包情形：
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背包是每種只有一件，完全背包是每種無限件，而多重背包是每種有限件。
我們現在主要是求解0-1背包，就是只有單副本的情形，并且只求價值的最大，沒有多余的限制條件諸如必須背包裝滿時的最大價值。
還是對于怎么考慮這個問題我不做太多說明，參看下面的鏈接。 [利用金礦模型理解背包] [本質是搜索的思想，只不過用打表存儲子問題的解]
下面我直接給出DP求解時的，四個關鍵點。 狀態f[ i ][ j ]：從前i個物品中選擇若干件，讓入承重為j的背包中所能達到的最大價值。 狀態轉移函數：f[ i ][ j ] = max( f[ i - 1 ][ j - w[i] ] + v[i] , f[ i - 1 ][ j ] ); 初始化：f[ i ][ 0 ] = 0 , i from 0 to N f[ 0 ][ j ] = 0 j from to M（這里有bug等會說） 結果：f[ N ][ M ]
補充：有助于理解 算法基本思想： 利用動態規劃思想 ，子問題為：f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。 其狀態轉移方程是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} //這個方程非常重要，基本上所有跟背包相關的問題的方程都是由它衍生出來的。 解釋一下上面的方程：“將前i件物品放入容量為v的背包中”這個子問題，如果只考慮第i件物品放或者不放，那么就可以轉化為只涉及前i-1件物品的問題， 即1、如果不放第i件物品，則問題轉化為“前i-1件物品放入容量為v的背包中”； 2、如果放第i件物品，則問題轉化為“前i-1件物品放入剩下的容量為v-c[i]的背包中”(此時能獲得的最大價值就是f [i-1][v-c[i]]再加上通過放入第i件物品獲得的價值w[i])。 則f[i][v]的值就是1、2中最大的那個值。
對于bug的說明：之所以是bug是因為這種條件并不通用。下面分析一下，這個bug搞了我一晚上。 就是對于初始化這么分析， 如果物品N==0，那么一件物品都沒有，價值肯定為0.所以f[ 0 ][ i ] = 0; 對于，背包的容量來說，按照常理如果背包的容量M==0。那么價值也一定為0，因為什么都放不進去，所以不會有價值。f[ i ][ 0 ] = 0;也就是說，這種情況下默認的是所有物品的容量都大于0。
但是，偏偏存在這樣的情況就是，人為假設存在容量為0的物品。那么當j==0時，這一列的值就不能被初始化為0了，因為把容量為0的物品放進去，此時就會有價值了。所形成的狀態表就會不一樣。
如果此時還是按照之前的方式初始化，就會出錯。因為顯然第0列的值都不一樣了，肯定會錯。 并且上面用理論給出了證明，第0列存在不為0的情形，只要存在容量為0的物品就好。
考慮這樣一組輸入： 背包容量為1，兩個物品。其中第一個物品的容量為0。 value: 1 2 cost: 0 1
給出兩種初始化的對比情況，只要你要明白一點。如果存在容量為0的物品，那么j==0時，這一列不能初始化為0.因為容量為0的物品可以放入容量為0的背包。導致價值不為0. 
第一個注意點（初始化考慮價值為0的物品）： 為了保證統一： 以后統統采用下面的形式，主要是修改了初始化的形式； 下面我直接給出DP求解時的，四個關鍵點。 狀態-f[ i ][ j ]：從前i個物品中選擇若干件，讓入承重為j的背包中所能達到的最大價值。 狀態轉移函數：f[ i ][ j ] = max( f[ i - 1 ][ j - w[i] ] + v[i] , f[ i - 1 ][ j ] ); 初始化：f[ i ][ 0 ] = 0 , i from 0 to N（只初始化第0行，因為什么物品都沒有價值一定為0） 結果：f[ N ][ M ]
第二個注意點（小心下標對應不一致帶來的問題。小心）： 對于轉移方程： f[ i ][ j ] = max( f[ i - 1 ][ j - w[i] ] + v[i] , f[ i - 1 ][ j ] )
上面公式中的w[i]和v[i]的意思是第i個物品的消耗和價值，默認下標是從1開始的。所以，如果下標不是從1開始開始。這兩個點需要修正。f[i][j]不需要修正，是因為他們考慮了容量為0和物品為0的情形。
修正下標的情形： f[ i ][ j ] = max( f[ i - 1 ][ j - w[i-1] ] + v[i-1] , f[ i - 1 ][ j ] )
[采藥]
沒有修正下標，因為直接從1開始
#include <iostream>#include <cstring>#include <utility>#define N 1000 // 總時間#define M 100 // 物品種類int w[M + 1];int v[M + 1];int f[M+1][N+1];int knapsack( int n, int m );int main( void ){ int n = 0, m = 0; while(std::cin >> n >> m){ memset(w, 0 , sizeof(w)); memset( v, 0, sizeof(v) ); for( int i = 1; i <= m; ++i ){ std::cin >> w[i] >> v[i]; } int ans = knapsack( n, m ); std::cout << ans << std::endl; } return 0;}int knapsack( int n, int m ){ memset( f, 0, sizeof(f) ); for( int i = 0; i <= n; ++i ) f[0][i] = 0; for( int i = 1; i <= m; ++i ){ for( int j = 0; j <= n; ++j ){//j=0，因為物品容量可能為0 if( w[i] <= j ) f[i][j] = std::max( f[i-1][j] , f[i-1][j-w[i]] + v[i] ); else f[i][j] = f[i-1][j]; } } return f[m][n];}第三個注意點：空間優化的問題 考察轉移方程： f[ i ][ j ] = max( f[ i - 1 ][ j - w[i] ] + v[i] , f[ i - 1 ][ j ] ) 每一行的修正只與上一行有關，根據這個特點，我們可以將原本的二維數組優化為一維。并且，由于f[i][j]的修正只與上一行當中左側的元素有關，所以可用如下方式完成狀態的轉移。并且從右至左更新。 dp[j] = max{ dp[j], dp[j-w[i]] + v[i] }
綜上，這個背包問題可以用如下算法求解：
zero_one_pack(v[i],c[i]) for j = M to c[i] f[j] = max( f[j-c[i]]+v[i] , f[j] )f[0......M] = 0; // 初始化第0行，即一個物品都沒有的情形。J一定要包括0.這是關鍵。for i = 1 to N zero_one_pack(v[i],w[i])上式當中，for j = M to c[i] 的優化很優雅。但是原始算法不能優化，因為全是0，還是需要把之前的值f[i-1][j]賦給f[i][j]，不然后者是0；變成滾動數組之后，就是原來的值。沒必要再賦值一遍。
[采藥]
參考這篇鏈接[lintcode-背包問題]
新聞熱點
疑難解答
