---

1. 問題引入

0-1 背包是比較經典的動態規劃問題，這里以代碼隨想錄里面的例子來介紹下。總的來說就是：有 n 個物品和一個重量為 w 的背包，這 n 個物品中第 i 個物品的重量為 w[i]，價值為 v[i]，那么這個背包能裝下的物品最大價值是多少，注意一個物品只能選一次。

2. 從 dfs 到動態規劃

我們來把問題具體化，假設現在有一個重量為 4 的背包，有 3 個物品，物品的重量和價值如下：

	重量	價值
物品 0	1	15
物品 1	3	20
物品 2	4	30

那么現在將物品裝入背包，能裝入的物品的最大價值是多少呢？要想解決動態規劃問題，我們總得從 dfs 入手，那就先從 dfs 講講。

public class Main {public static void main(String[] args) {Main main = new Main();main.findMax(new int[]{1, 3, 4}, new int[]{15, 20, 30}, 4);main.findMax(new int[]{1, 3}, new int[]{15, 20}, 3);}public void findMax(int[] weight, int[] prices, int max){int res = dfs(weight, prices, max, weight.length - 1);System.out.println("最大價值是: " + res);}private int dfs(int[] weight, int[] prices, int max, int i) {if(i < 0){// 遍歷到尾部了return 0;}// 不選當前的價值int noPick = dfs(weight, prices, max, i - 1);// 如果剩余重量大于 weight[i] 才可選return max >= weight[i] ? Math.max(prices[i] + dfs(weight, prices, max - weight[i], i - 1), noPick) : noPick;}
}

dfs 的遍歷邏輯很簡單，就是從后往前遍歷，然后對于當前物品，可以選或者不選，但是有條件，如果選的話剩余的容量必須要大于 weight[i]，否則就不能選，因為剩余重量裝不下當前物品。

但是我們知道，這個方法是會超時的，如果數組長度比較大，因為里面有不少重復計算，既然這樣我們就加上記憶化搜索。

public class Main {public static void main(String[] args) {Main main = new Main();main.findMax(new int[]{1, 3, 4}, new int[]{15, 20, 30}, 4);main.findMax(new int[]{1, 5}, new int[]{15, 20}, 3);}public void findMax(int[] weight, int[] prices, int max){// memo[i][j] 的意思是從 [0...i] 中將物品放到重量為 j 的背包，最大值是多少int[][] memo = new int[weight.length][max + 1];for (int[] arr : memo) {Arrays.fill(arr, -1);}int res = dfs(weight, prices, max, weight.length - 1, memo);System.out.println("最大價值是: " + res);}private int dfs(int[] weight, int[] prices, int max, int i, int[][] memo) {if(i < 0){// 遍歷到尾部了return 0;}if(memo[i][max] != -1){return memo[i][max];}// 不選當前的價值int noPick = dfs(weight, prices, max, i - 1, memo);return memo[i][max] = (max >= weight[i] ? Math.max(prices[i] + dfs(weight, prices, max - weight[i], i - 1, memo), noPick) : noPick);}
}

好了，在記憶化搜索的基礎上，我們再來改造成動態規劃，首先我們看上面的 dfs 邏輯，當前 i 的結果是基于 i - 1 得來的，也就是說我們可以得到下面的遞推公式：

• $dp[i][j]=Math.max(dp[i?1][j],prices[i]+dp[i?1][j?weight[i]])$
• 上面的意思是如果不選當前下標 i 的物品，那么就繼續往前找
• 如果選當前下標 i 的物品，那么價值就是 prices[i]，接著 j 要減去物品 i 的價值

好了，遞推公式有了，那么如何初始化呢？我們知道 dp[i][j] 的意思是：在下標 [0…i] 中選擇物品裝入重量為 j 的背包，能裝入的最大值是多少！

• 當 i = 0 的時候，dp[0][j] 表示下標 0 物品裝入重量為 j 的背包，最大值是多少。
• 當 j = 0 的時候，dp[i][0] 表示下標 [0…i] 的物品裝入重量為 0 的背包，最大值是多少，自然是 0 了。

所以初始化如下：

int[][] dp = new int[weight.length][max + 1];
for(int j = 0; j <= max; j++){if(j > weight[0]){dp[0][j] = prices[i];}
}

下面再結合記憶化搜索的代碼，就能寫出來下面的動態規劃代碼。

public int findMaxD(int[] weight, int[] prices, int max){int[][] dp = new int[weight.length][max + 1];for(int j = 0; j <= max; j++){if(j >= weight[0]){dp[0][j] = prices[0];}}// 遍歷物品for(int i = 1; i < weight.length; i++){// 遍歷背包for(int j = 0; j <= max; j++){if(j < weight[i]){dp[i][j] = dp[i - 1][j];} else {dp[i][j] = Math.max(dp[i - 1][j], prices[i] + dp[i - 1][j - weight[i]]);}}}return dp[weight.length - 1][max];
}

3. 動態規劃過程分析

上面我們寫出了動態規劃的代碼，但是不知道大家有沒有疑問，就是這個物品和背包的遍歷是有順序的嗎？注意我這里指的是二維的 dp 數組，現在我們討論都是在二維 dp 的基礎上去討論，后面會逐步演變成一維 dp。

首先就是遞推公式

• $dp[i][j]=Math.max(dp[i?1][j],prices[i]+dp[i?1][j?weight[i]])$，根據這個遞推公式，

通過這個遞推公式，我們能發現 dp[i][j] 其實依賴當前格子的上邊和左上的格子。

那么從這個角度，我們再來看動態規劃的初始化，你就知道為什么要初始化 i = 0 和 j = 0 的格子值了（j = 0 不需要初始化，因為都是 0）。

初始化完第一行之后，再從第二行開始通過遞推公式填充格子，最終填充好的結果如下所示：

我用下標 （1，3）舉個例子，當 i = 1，j = 3 的時候，如果不選當前物品，那么就是 dp[0][3]，如果選當前物品，那么就是 dp[1 - 1][3 - 3] + 20 = 20，兩者取最大值就是 20，遍歷順序是從左到右，從上到下。

4. 二維 dp 的遍歷順序

好了，上面我們解析了 dp 數組的填充過程，那么如果是先遍歷物品，再遍歷背包，填充的過程就是 從左到右，從上到下。那么如果是先遍歷背包，再遍歷物品呢？

還是回到 dp 圖，如果先遍歷背包，再遍歷物品，其實就是從從上到下，從左到右。

那么我們想一下，如果是這種遍歷順序，在遍歷到 dp[1][3] 的時候，dp[0][3] 和 dp[0][0] 初始化了嗎，換句話說，當遍歷到第 i 行的時候，第 i - 1 行初始化了嗎？

從遍歷過程就能看到，其實是初始化了的，所以我們先遍歷背包，再遍歷物品也是沒問題的。如何遍歷，遍歷順序是什么就取決于當遍歷到（i，j）的時候，需要依賴的格子有沒有初始化。

public int findMaxD(int[] weight, int[] prices, int max) {int[][] dp = new int[weight.length][max + 1];for (int j = 0; j <= max; j++) {if (j >= weight[0]) {dp[0][j] = prices[0];}}// 遍歷背包for (int j = 0; j <= max; j++) {// 遍歷物品for (int i = 1; i < weight.length; i++) {if (j < weight[i]) {dp[i][j] = dp[i - 1][j];} else {dp[i][j] = Math.max(dp[i - 1][j], prices[i] + dp[i - 1][j - weight[i]]);}}}return dp[weight.length - 1][max];
}

那么我再問一句，遍歷背包能倒敘遍歷嗎？其實從 dp 數組的依賴就能看出，可以！！！ 因為第 i 行的數據只和第 i - 1 行有關，和本行無關，而我們知道 dp 數組在處理到第 i 行的時候 i - 1就已經處理好了，所以愛怎么遍歷就怎么遍歷。

5. 從二維數組到一維數組

上面我們使用二維數組對 dp 進行填充了，但是大家有沒有注意到，第 i 行的結果只依賴第 i - 1 行，所以我們完全可以只使用一維數組，把 i 省略掉。相當于把 i 的結果粘貼到 i - 1行的位置，所以 dp[i] 就表示重量為 i 的容量能裝入的最大物品價值是多少 ，大體過程如下：

• 初始化 dp[0]
• 根據 dp[0] 初始化 dp[1]
• …

初始化 dp[0] 的時候，重量為 0 的背包肯定是放不下任何物品的，所以不需要初始化，下面看遍歷邏輯。

public int findMax(int[] weight, int[] prices, int max){int[] dp = new int[max + 1];// 遍歷物品for(int i = 0; i < weight.length; i++){// 遍歷背包for(int j = max; j >= weight[i]; j--){dp[j] = Math.max(dp[j], dp[j - weight[i]] + prices[i]);}}return dp[max];
}

注意下 dp 公式為：

• $dp[j]=Math.max(dp[j],dp[j?weight[i]]+prices[i])$

大家可能好奇為什么可以直接和 dp[j] 做比較，我把二維數組的 dp 粘貼過來。

dp 數組初始化為 0，當 i = 0 的時候，其實就是在初始化第一行 [0，15，15，15，15]。當 i = 1 的時候，記住此時 dp 記錄的是 i = 0 的結果，那么 dp[j] = Math.max(dp[j], dp[j - weight[i]] + prices[i]) 其實就是在根據 i = 0 來更新 i = 1 的數據，一直這樣遍歷下去，遍歷到最后就是我們要的結果了。

6. 一維數組的遍歷次序

上面一維數組的遍歷次序是先遍歷物品，再遍歷背包，那么可以先遍歷背包，再遍歷物品嗎？也就是下面的寫法。

// 遍歷背包
for (int j = max; j >= 0; j--) {// 遍歷物品for (int i = 0; i < weight.length; i++) {if (j >= weight[i]) {dp[j] = Math.max(dp[j], dp[j - weight[i]] + prices[i]);}}
}

讓我們看下這個過程，當 j = 4 的時候，遍歷所有物品，求 dp[j] 能放下的物品的最大價值，為什么我說求 dp[j] 的最大價值，因為是倒敘遍歷，同時又是 j 在外層一直往前遍歷，所以 dp[j - weight[i]] 你就當成 0 就好了，相當于 dp[j] = Math.max(dp[j], prices[i])。

所以最終求出來的結果就是當前這個重量下能放下的物品的最大價值（單個）。

所以這里的遍歷順序就得是：先遍歷物品，再遍歷背包。

7. 背包的遍歷順序

public int findMax(int[] weight, int[] prices, int max){int[] dp = new int[max + 1];// 遍歷物品for(int i = 0; i < weight.length; i++){// 遍歷背包for(int j = max; j >= weight[i]; j--){dp[j] = Math.max(dp[j], dp[j - weight[i]] + prices[i]);}}return dp[max];
}

繼續回到遍歷邏輯，注意到背包是從后往前遍歷的，那么為什么不能從前往后遍歷呢？

我們仔細看下 dp 的意義，由于從二維降到一維，我們在遍歷的時候是不斷用新獲取的 dp[j] 覆蓋原來的 dp[j]，還是從二維數組的 dp 看下。

我上面說的意思相當于說，現在一維 dp 的數組是物品 0 所在的這行數據 [0，15，15，15，15]。當 i = 1 的時候，求出來的 20 會立馬覆蓋回數組，這時候數組是 [0，15，15，20，15]，j = 3，繼續往前遍歷。

而如果緩存背包從前往后遍歷，結果會是怎么樣呢？我把物品的重量和價格粘貼過來。

	重量	價值
物品 0	1	15
物品 1	3	20
物品 2	4	30

這次我們就看 i = 0 的遍歷結果，初始化數組全是 0。

• dp[0] = 0
• dp[1] = Math.max(dp[1], dp[1-weight[0]] + prices[0]) = 15
• dp[2] = Math.max(dp[2], dp[2-weight[0]] + prices[0]) = 30
• dp[3] = Math.max(dp[3], dp[3-weight[0]] + prices[0]) = 45
• …

最終結果就變成了：

其實出現這種情況，就是完全背包的做法了，也就是一個物品被選擇了多個。

那么為什么會出現這種情況呢？其實我們還是可以從一維 dp 入手。

• $dp[j]=Math.max(dp[j],dp[j?weight[i]]+prices[i])$

上面是一維的公式，假設現在數字組初始化為 0，那么在初始化 i = 0 的時候假設初始化了 dp[1] = 15，大家記住，這里的 dp 是實時覆蓋的，所以這時候的狀態如下：

這時候 dp[0] 和 dp[1] 都計算過了并且覆蓋會原數組下標，而 dp[2]、dp[3]、dp[4] 還保留初始化的狀態，啥意思呢，換成 i - 1 和 i，意思就是這時候 dp[0] 和 dp[1] 是 i = 1 計算出來的，而 dp[2]、dp[3]、dp[4] 則還是 dp[i-1] 的狀態。

我們接下來繼續看 dp[2]，我們知道 dp[2] = Math.max(dp[2], dp[1] + 15) = 30，意思就是在計算 dp[2] 的時候使用到了 dp[1]，而這個 dp[1] 已經被覆蓋過了，意思就是這個 dp[1] 不是 i - 1 的值了，而是 i 的值，所以就造成了多次選擇。

在二維數組中計算 dp[i] 的時候是使用 dp[i-1] 的值，因為不會被覆蓋，所以遍歷順序就無所謂。但是一維數組就不一樣的，因為會實時覆蓋，所以只能從后往前遍歷，否則就會用前面已經計算過的值來計算當前下標的值了。

8. 代碼總結

好了，到這里我們就解析完0-1背包了，分為二維和一維，其實說了這么多，大家只需要記住兩個版本就行了。

public int findMaxD(int[] weight, int[] prices, int max){int[][] dp = new int[weight.length][max + 1];for(int j = 0; j <= max; j++){if(j >= weight[0]){dp[0][j] = prices[0];}}// 遍歷物品for(int i = 1; i < weight.length; i++){// 遍歷背包for(int j = 0; j <= max; j++){if(j < weight[i]){dp[i][j] = dp[i - 1][j];} else {dp[i][j] = Math.max(dp[i - 1][j], prices[i] + dp[i - 1][j - weight[i]]);}}}return dp[weight.length - 1][max];
}

一維的遍歷如下：

public int findMax(int[] weight, int[] prices, int max){int[] dp = new int[max + 1];// 遍歷物品for(int i = 0; i < weight.length; i++){// 遍歷背包for(int j = max; j >= weight[i]; j--){dp[j] = Math.max(dp[j], dp[j - weight[i]] + prices[i]);}}return dp[max];
}

9. 總結

我們總結下二維數組和一維數組的遍歷順序：

• 二維數組

  • 背包和物品的遍歷順序可以顛倒
  • 遍歷背包的時候可以正序和倒敘遍歷

• 一維數組

  • 先遍歷物品，再遍歷背包
  • 遍歷背包需要倒敘遍歷

如有錯誤，歡迎指出！！！