十分感謝這位大大的講解！ http://blog.csdn.net/liuqiyao_01/article/details/8521776

接下來為個人對01背包問題的理解：

每種物品數(shù)量均為1，每個物品都包含體積weight和價值value，而有一個Weight大小的背包，怎么裝才能讓這個背包里的總價值Value最大

首先，我們可以有下面這段代碼： dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);

i為當前選取第i個物品，j為體積。 那么dp[i][j]的含義為，不選取這件物品（dp[i-1][j]）和選取這件物品（dp[i-1][j-weight[i]]+value[i]）的最大值。

后面選取這件物品可能有些難理解，我們解析一下。

這個j為什么是個變量？ 因為當你選取了一個物品時，背包的體積就會改變?yōu)閃eight-weight[i]，所以從0（背包為滿）到Weight（背包為空）這些都是可能發(fā)生的情況。

而這個dp[i-1][j-weight[i]]是什么含義？ 當你選取了第i個物品，你需要將這個物品的weight[i]從j中減去，j-weight[i]就是當前剩余的體積，dp[i-1][j-weight[i]]就是選取第i個物品之前的（j-weight[i]）的最大價值。

這兩個難點搞定了之后，我們就有了下面的代碼：

當選取第n個物品，背包大小為Weight的情況下，總價值的最大值就是dp[n][Weight]了。

注意這里采用的是二維數(shù)組，但我們可以用一維數(shù)組來節(jié)省空間。

注意到j(luò)的循環(huán)從正序變?yōu)榈剐颍蚴钱攋從大到小時，較小的j仍保存的是上一次循環(huán)的值，使用時相當于dp[i-1][j-weight[i]]，若改為順序的話，較小的j被更新為dp[i][j-weight[i]]，與原來的順序不符。