本專欄已參加蓄力計(jì)劃，感謝讀者支持?

往期文章

一. Java入門算法（貪心篇）丨蓄力計(jì)劃
二. Java入門算法（暴力篇）丨蓄力計(jì)劃
三. Java入門算法（排序篇）丨蓄力計(jì)劃
四. Java入門算法（遞歸篇）丨蓄力計(jì)劃
五. Java入門算法（雙指針篇）丨蓄力計(jì)劃
六. Java入門算法（數(shù)據(jù)結(jié)構(gòu)篇）丨蓄力計(jì)劃
七. Java入門算法（滑動(dòng)窗口篇）丨蓄力計(jì)劃
八. Java入門算法（動(dòng)態(tài)規(guī)劃篇1：初識(shí)動(dòng)規(guī)）
九. Java入門算法（動(dòng)態(tài)規(guī)劃篇2：01背包精講）

---

動(dòng)態(tài)規(guī)劃篇2

• 往期文章
• 01背包
• • 問題描述
  • 分析
  • 進(jìn)階

---

01背包

網(wǎng)上有非常多的文章對(duì)01背包進(jìn)行講解，變量名繁雜，對(duì)初學(xué)者不怎么友好。在這篇文章里，我盡量講得簡單，不作一些多余的贅述。

不會(huì)有人不知道背包是什么吧？

---

問題描述

???????把n種物品裝進(jìn)一個(gè)背包，物品 i 的重量是w[ i ]，價(jià)值是c[ i ]，背包的容量是M，求能裝進(jìn)背包的最大總價(jià)值。

注：w是存儲(chǔ)n個(gè)物品的重量的數(shù)組，c是存儲(chǔ)n個(gè)物品的價(jià)值的數(shù)組

---

分析

為啥叫01背包呢？因?yàn)閷?duì)于每件物品，只有 不拿（0） 與 拿（1） 兩種狀態(tài)。

動(dòng)態(tài)規(guī)劃解01背包，關(guān)鍵是填二維表dp：

• 行 i 指的是我們當(dāng)前要考慮裝 i 個(gè)物品
• 列 j 表示的是背包剩余容量
• dp [i] [j] 的值是指 i 個(gè)物品裝進(jìn)容量為 j 的背包的最大總價(jià)值

當(dāng) i 等于物品總量n、j 等于背包容量M的時(shí)候，dp [i] [j] 的值就是問題的解。下面根據(jù)例子輸入，邊填表邊分析。

輸入：n = 4， M = 10 w[] = [2, 3, 4, 7] c[] = [1, 3, 5, 9] (4個(gè)物品裝進(jìn)容量為10的背包)

• 初始化第0行為全0，沒有物品，不管容量多大，價(jià)值只能是0
• 初始化第0列為全0，容量為0，裝不下任何物品，價(jià)值只能是0

---

現(xiàn)在只考慮裝 1 件物品（i = 1）

• dp[1][1] = 0，容量為1的背包裝不下第 1 件物品，因?yàn)樗闹亓繛?

---

• dp[1][2] = 1，此時(shí)容量為2的背包可以裝下物品1，而它的價(jià)值為1

---

• 第1行后面容量>1的背包，都可以裝下物品1，因此它們的價(jià)值都為1

---

現(xiàn)在考慮的是裝 2 件物品（i = 2）

• dp[2][1] = 0，容量為1的背包即裝不下物品1（重量2）也裝不下物品2（重量3）

---

• 容量為2的背包裝不下物品2，但可以裝下物品1
• 因此dp[2][2] = dp[1][2] = 1

此時(shí)引出第一種情況:

當(dāng)背包容量小于物品 i 的重量 w[i] 時(shí)，拿不了物品 i ，所以考慮拿 i - 1個(gè)物品的最大總價(jià)值。

得到狀態(tài)轉(zhuǎn)移方程: dp[i][j] = dp[ i - 1][j] ( j < w[i])

if (j < w[i]) {dp[i][j] = dp[i - 1][j];}

---

• 容量為3的背包既可以裝下物品2、也可以裝下物品1。要使價(jià)值最大，我們肯定會(huì)選裝物品2，這樣就是dp[2][3] = 3。
• 此時(shí)的背包容量都用來裝物品2，已經(jīng)滿了，裝不下物品1（對(duì)應(yīng)dp[1][0] = 0）。
• 但這只是我們主觀得出的選擇，計(jì)算機(jī)怎么知道是選裝物品1還是物品2呢？

此時(shí)引出第二種情況：

當(dāng)背包容量大于物品 i 的重量 w[i] 時(shí)，可以拿物品 i ，此時(shí)需要考慮拿了物品 i 的價(jià)值大，還是不拿物品 i 的價(jià)值大

不拿物品 i ，就是第一種情況，考慮拿 i - 1個(gè)物品的最大總價(jià)值

拿物品 i ，就需要把物品 i 裝入到背包（+c[i]）。但！還需要考慮裝完物品 i 的背包還可以裝多少（+ dp[ i - 1][ j - w[i]]，即上述的 dp[1][0]）

得到狀態(tài)轉(zhuǎn)移方程: dp[i][j] = c[i] + dp[ i - 1][ j - w[i]] ( j >= w[i])

---

如下，容量為5的背包，兩個(gè)物品都可以裝下

所以dp[2][5] = c[2] + dp[1][5 - 3] 即 4 = 3 + 1

if (j >= w[i]) {dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + c[i]);}

綜上，可以得到總的狀態(tài)轉(zhuǎn)移方程：

$$dp[i][j]=dp[i?1][j]，(j<w[i])$$
$$dp[i][j]=c[i]+dp[i?1][j?w[i]]，(j>=w[i])$$
狀態(tài)轉(zhuǎn)移方程代表了我們接下來的選擇，根據(jù)它計(jì)算出表內(nèi)的所有值，如下圖

時(shí)間復(fù)雜度為O（n²），空間復(fù)雜度為O（M*n）

得到題目答案：12

完整代碼

// 二維dppublic static int dp_2d(int n, int[] w, int[] c, int M) {int[][] dp = new int[n + 1][M + 1];for (int i = 1; i < n + 1; ++i) {for (int j = 1; j < M + 1; ++j) {if (j < w[i]) {dp[i][j] = dp[i - 1][j];}else{dp[i][j] = Math.max(dp[i - 1][j], c[i] + dp[i - 1][j - w[i]]);}}}return dp[n][M];}

---

進(jìn)階

滾動(dòng)數(shù)組

• 由上述的填表順序可以發(fā)現(xiàn)，每次 dp[i][j] 的值都是由 i - 1 行左上方或正上方的dp值得出。因此可以嘗試把 [i] 這一維度去除，二維dp降成一維dp，通過不斷刷新一維dp表的值，模擬上述二維dp的填表過程。時(shí)間復(fù)雜度仍為O(n^2^)，空間復(fù)雜度降為O（M）。
• 但會(huì)發(fā)現(xiàn)若按照從左往右的順序填表，會(huì)把需要用到的值覆蓋，固填表方向需要反過來。

完整代碼

// 二維降一維，滾動(dòng)數(shù)組public static int dp_1d(int n, int[] w, int[] c, int M) {int[] dp = new int[M + 1];for (int i = 1; i < n + 1; ++i) {for (int j = 1; j < M + 1; ++j) {if (j >= w[i]) {dp[j] = Math.max(dp[j], dp[j - w[i]] + c[i]);}}}return dp[M];}

---

END

參考資料：
https://www.bilibili.com/video/BV1C7411K79wfrom=search&seid=9137630755457139754

總結(jié)

以上是生活随笔為你收集整理的Java入门算法（动态规划篇2：01背包精讲）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。