---

1. 問(wèn)題引入

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

2. 從 dfs 到動(dòng)態(tài)規(guī)劃

我們來(lái)把問(wèn)題具體化，假設(shè)現(xiàn)在有一個(gè)重量為 4 的背包，有 3 個(gè)物品，物品的重量和價(jià)值如下：

	重量	價(jià)值
物品 0	1	15
物品 1	3	20
物品 2	4	30

那么現(xiàn)在將物品裝入背包，能裝入的物品的最大價(jià)值是多少呢？要想解決動(dòng)態(tài)規(guī)劃問(wèn)題，我們總得從 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("最大價(jià)值是: " + res);}private int dfs(int[] weight, int[] prices, int max, int i) {if(i < 0){// 遍歷到尾部了return 0;}// 不選當(dāng)前的價(jià)值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 的遍歷邏輯很簡(jiǎn)單，就是從后往前遍歷，然后對(duì)于當(dāng)前物品，可以選或者不選，但是有條件，如果選的話剩余的容量必須要大于 weight[i]，否則就不能選，因?yàn)槭Ｓ嘀亓垦b不下當(dāng)前物品。

但是我們知道，這個(gè)方法是會(huì)超時(shí)的，如果數(shù)組長(zhǎng)度比較大，因?yàn)槔锩嬗胁簧僦貜?fù)計(jì)算，既然這樣我們就加上記憶化搜索。

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("最大價(jià)值是: " + 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];}// 不選當(dāng)前的價(jià)值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);}
}

好了，在記憶化搜索的基礎(chǔ)上，我們?cè)賮?lái)改造成動(dòng)態(tài)規(guī)劃，首先我們看上面的 dfs 邏輯，當(dāng)前 i 的結(jié)果是基于 i - 1 得來(lái)的，也就是說(shuō)我們可以得到下面的遞推公式：

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

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

• 當(dāng) i = 0 的時(shí)候，dp[0][j] 表示下標(biāo) 0 物品裝入重量為 j 的背包，最大值是多少。
• 當(dāng) j = 0 的時(shí)候，dp[i][0] 表示下標(biāo) [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];}
}

下面再結(jié)合記憶化搜索的代碼，就能寫出來(lái)下面的動(dòng)態(tài)規(guī)劃代碼。

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. 動(dòng)態(tài)規(guī)劃過(guò)程分析

上面我們寫出了動(dòng)態(tài)規(guī)劃的代碼，但是不知道大家有沒(méi)有疑問(wèn)，就是這個(gè)物品和背包的遍歷是有順序的嗎？注意我這里指的是二維的 dp 數(shù)組，現(xiàn)在我們討論都是在二維 dp 的基礎(chǔ)上去討論，后面會(huì)逐步演變成一維 dp。

首先就是遞推公式

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

通過(guò)這個(gè)遞推公式，我們能發(fā)現(xiàn) dp[i][j] 其實(shí)依賴當(dāng)前格子的上邊和左上的格子。

那么從這個(gè)角度，我們?cè)賮?lái)看動(dòng)態(tài)規(guī)劃的初始化，你就知道為什么要初始化 i = 0 和 j = 0 的格子值了（j = 0 不需要初始化，因?yàn)槎际?0）。

初始化完第一行之后，再?gòu)牡诙虚_始通過(guò)遞推公式填充格子，最終填充好的結(jié)果如下所示：

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

4. 二維 dp 的遍歷順序

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

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

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

從遍歷過(guò)程就能看到，其實(shí)是初始化了的，所以我們先遍歷背包，再遍歷物品也是沒(méi)問(wèn)題的。如何遍歷，遍歷順序是什么就取決于當(dāng)遍歷到（i，j）的時(shí)候，需要依賴的格子有沒(mé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 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];
}

那么我再問(wèn)一句，遍歷背包能倒敘遍歷嗎？其實(shí)從 dp 數(shù)組的依賴就能看出，可以！！！ 因?yàn)榈?i 行的數(shù)據(jù)只和第 i - 1 行有關(guān)，和本行無(wú)關(guān)，而我們知道 dp 數(shù)組在處理到第 i 行的時(shí)候 i - 1就已經(jīng)處理好了，所以愛(ài)怎么遍歷就怎么遍歷。

5. 從二維數(shù)組到一維數(shù)組

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

• 初始化 dp[0]
• 根據(jù) dp[0] 初始化 dp[1]
• …

初始化 dp[0] 的時(shí)候，重量為 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] 做比較，我把二維數(shù)組的 dp 粘貼過(guò)來(lái)。

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

6. 一維數(shù)組的遍歷次序

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

// 遍歷背包
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]);}}
}

讓我們看下這個(gè)過(guò)程，當(dāng) j = 4 的時(shí)候，遍歷所有物品，求 dp[j] 能放下的物品的最大價(jià)值，為什么我說(shuō)求 dp[j] 的最大價(jià)值，因?yàn)槭堑箶⒈闅v，同時(shí)又是 j 在外層一直往前遍歷，所以 dp[j - weight[i]] 你就當(dāng)成 0 就好了，相當(dāng)于 dp[j] = Math.max(dp[j], prices[i])。

所以最終求出來(lái)的結(jié)果就是當(dāng)前這個(gè)重量下能放下的物品的最大價(jià)值（單個(gè)）。

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

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];
}

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

我們仔細(xì)看下 dp 的意義，由于從二維降到一維，我們?cè)诒闅v的時(shí)候是不斷用新獲取的 dp[j] 覆蓋原來(lái)的 dp[j]，還是從二維數(shù)組的 dp 看下。

我上面說(shuō)的意思相當(dāng)于說(shuō)，現(xiàn)在一維 dp 的數(shù)組是物品 0 所在的這行數(shù)據(jù) [0，15，15，15，15]。當(dāng) i = 1 的時(shí)候，求出來(lái)的 20 會(huì)立馬覆蓋回?cái)?shù)組，這時(shí)候數(shù)組是 [0，15，15，20，15]，j = 3，繼續(xù)往前遍歷。

而如果緩存背包從前往后遍歷，結(jié)果會(huì)是怎么樣呢？我把物品的重量和價(jià)格粘貼過(guò)來(lái)。

	重量	價(jià)值
物品 0	1	15
物品 1	3	20
物品 2	4	30

這次我們就看 i = 0 的遍歷結(jié)果，初始化數(shù)組全是 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
• …

最終結(jié)果就變成了：

其實(shí)出現(xiàn)這種情況，就是完全背包的做法了，也就是一個(gè)物品被選擇了多個(gè)。

那么為什么會(huì)出現(xiàn)這種情況呢？其實(shí)我們還是可以從一維 dp 入手。

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

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

這時(shí)候 dp[0] 和 dp[1] 都計(jì)算過(guò)了并且覆蓋會(huì)原數(shù)組下標(biāo)，而 dp[2]、dp[3]、dp[4] 還保留初始化的狀態(tài)，啥意思呢，換成 i - 1 和 i，意思就是這時(shí)候 dp[0] 和 dp[1] 是 i = 1 計(jì)算出來(lái)的，而 dp[2]、dp[3]、dp[4] 則還是 dp[i-1] 的狀態(tài)。

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

在二維數(shù)組中計(jì)算 dp[i] 的時(shí)候是使用 dp[i-1] 的值，因?yàn)椴粫?huì)被覆蓋，所以遍歷順序就無(wú)所謂。但是一維數(shù)組就不一樣的，因?yàn)闀?huì)實(shí)時(shí)覆蓋，所以只能從后往前遍歷，否則就會(huì)用前面已經(jīng)計(jì)算過(guò)的值來(lái)計(jì)算當(dāng)前下標(biāo)的值了。

8. 代碼總結(jié)

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

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. 總結(jié)

我們總結(jié)下二維數(shù)組和一維數(shù)組的遍歷順序：

• 二維數(shù)組

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

• 一維數(shù)組

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

如有錯(cuò)誤，歡迎指出！！！