今天是動態(tài)規(guī)劃的第三天癌蚁！來到了萬眾矚目的 背包問題幻梯！
首先，什么是背包問題努释？簡單來說就是有一個(gè)背包，容量已知咬摇，然后有幾個(gè)物品伐蒂，已知物品的重量與價(jià)值，求如何放物品使得背包內(nèi)物品的價(jià)值最高肛鹏。根據(jù)物品的數(shù)量可以把背包問題細(xì)分為01背包和完全背包等更細(xì)的分類：
鑒于01背包是各類背包問題的核心基礎(chǔ)逸邦，因此本篇優(yōu)先探索01背包問題的核心解法及其內(nèi)在邏輯。
01背包??問題概述：有n件物品和一個(gè)最多能裝w重量的背包在扰。第i件物品的重量為weight[i]缕减、價(jià)值為value[i]。每件物品最多只能用一次芒珠。求解將那些物品裝入背包里 可使得背包總價(jià)值最大桥狡？
看到問題，首先我們得想到的是 這個(gè)問題的暴力解法應(yīng)該是如何皱卓？這點(diǎn)其實(shí)不難想裹芝，對于每個(gè)物品，其實(shí)就是選與不選兩種情況娜汁，因此我們可以用回溯法搜索出所有的情況嫂易，對于n個(gè)物品而言，時(shí)間復(fù)雜度是O(2 ^ n)掐禁。所以暴力解法不是做不出來怜械，而是他是指數(shù)級別的復(fù)雜度颅和，所以需要動態(tài)規(guī)劃來優(yōu)化。
下面以一個(gè)例子來講解：
背包重量為4缕允，
物品0 重量1 價(jià)值15
物品1 重量3 價(jià)值20
物品2 重量4 價(jià)值30
求背包的最大價(jià)值峡扩。
解法是 二維dp數(shù)組解法：
還是用動態(tài)規(guī)劃五部曲來分析一下：
-
在分析二維數(shù)組的含義之前，我們現(xiàn)探究一下為什么要使用二維數(shù)組---因?yàn)槲覀冇袃蓚€(gè)維度需要表示---物品 和 背包容量灼芭。如圖所示有额，二維數(shù)組為dp[i][j]:
二維數(shù)組dp[i][j]
由圖可知，我們使用i表示物品彼绷，j表示背包容量/背包重量巍佑。（當(dāng)然這只是習(xí)慣問題，你也可以用j來表示物品）寄悯。根據(jù)動態(tài)規(guī)劃 是 通過子問題的求解推導(dǎo)出整體的最優(yōu)解 的思路萤衰，我們可以一步步嘗試填寫一下表格：例如把物品0放入背包：
物品0放入背包
因?yàn)槲锲?只有一個(gè)，所以最多就只能放一次猜旬，這是為什么當(dāng)容量>=2之后脆栋，總價(jià)值依然是15的原因。接下來嘗試把物品1放入背包：
物品1放入背包
背包容量為3時(shí)洒擦，可選擇放物品0或物品1椿争，顯然放物品1的價(jià)值更高，所以選擇放物品1或取更高的價(jià)值20.
背包容量為4時(shí)熟嫩，上一行狀態(tài)不變秦踪，背包只能放物品0；這一行除了物品0之外還有物品1可以選掸茅，而且可以兩者都放得下椅邓，所以最高價(jià)值為35.
由以上例子的分析，我們不難發(fā)現(xiàn)dp數(shù)組的含義：dp[i][j]表示在[0-i]的物品里任意選擇昧狮，放進(jìn)容量為j的背包景馁，所產(chǎn)生的最大價(jià)值。舉例說明：在上圖中dp[1][4]表示在物品0和物品1里任意選擇逗鸣，使得放入容量為4的背包時(shí) 產(chǎn)生的最大價(jià)值合住。
-
遞推公式
這一步就是要確定dp[i][j]可由哪些方向推到而來。還是用dp[1][4]舉例慕购，對于物品1而已有兩種情況：1??把物品1放入背包 2??不把物品1放入背包
如果不把物品1放入背包聊疲，那么背包的價(jià)值應(yīng)該是dp[0][4]，即容量為4時(shí)沪悲，只考慮是否放物品0 的最大價(jià)值：
不放物品1時(shí)背包價(jià)值的推導(dǎo)方向
如果把物品1放入背包获洲，那么價(jià)值應(yīng)該是物品1的價(jià)值 加上 背包剩余容量時(shí)考慮是否放入物品0的價(jià)值。帶入數(shù)值就是 背包剩余容量1時(shí)殿如，是否放入物品0的價(jià)值dp[0][1]:
因此贡珊，我們只需將兩種方式取最大值 即可 求的 放與不放物品1的最大值：
dp[1][4] = max(dp[0][4], dp[0][1] + value[1])
將以上公式抽象化可以得到 不放物品i的價(jià)值為 dp[i-1][j]最爬；放物品i的價(jià)值為dp[i-1][j-weight[i]] + value[i]
綜上所述，遞推公式為 dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])
-
dp數(shù)組的初始化
關(guān)于初始化门岔，不是瞎貓碰上死耗子爱致，胡亂一猜。一定要與定義吻合寒随。
從dp[i][j]的定義出發(fā)糠悯，當(dāng)背包容量為0時(shí)，無論物品有哪些妻往，價(jià)值都是為0：
背包容量為0時(shí)的初始化
由遞推公式可知 i 都是由 i-1 推導(dǎo)而來互艾，也就是圖中的下一層都是由上一層的某一個(gè)推導(dǎo)而來，因此第一行的數(shù)據(jù)讯泣，即i=0時(shí)纫普，就一定要初始化。對此也不難好渠，當(dāng)容量不足以放物品0時(shí)昨稼，價(jià)值也就不存在；當(dāng)重量足夠放物品0時(shí)拳锚，價(jià)值一直時(shí)物品0的價(jià)值假栓。
dp數(shù)組第一行初始化
至于其他部分，鑒于在后續(xù)遍歷中都會被覆蓋霍掺，因此是多少都無所謂但指，所以為了方便我們就都初始化為0就好了。
完整的dp數(shù)組初始化 -
確定遍歷順序抗楔。
從圖中可以看出，遍歷有兩個(gè)維度：物品 和 背包重量拦坠。至于兩個(gè)維度先遍歷哪個(gè)连躏，我們得理解遞推方向的本質(zhì)。
根據(jù)遞推公式 dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]) 可以看出dp[i][j]是由dp[i-1][j]和dp[i-1][j-weight[i]]推出來的贞滨。而這兩部分都在dp[i][j]的左上部分（包括正上方）入热，所以只需保證在求得dp[i][j]之前，左上部分（包括正上方）是有值的就可以了晓铆。接下來我們看看兩種遍歷順序能否保證dp[i][j]左上方有值勺良。
1??先遍歷物品后遍歷背包容量
先遍歷物品
可以看到，遍歷順序是骄噪，從左到右尚困，然后一行一行向下遍歷（圖中藍(lán)色箭頭）那在遍歷到紅框時(shí)，他的左上部分時(shí)已經(jīng)有值了的链蕊，所以這種遍歷方式可行事甜。
2??先遍歷背包容量后遍歷物品
先遍歷背包容量
遍歷順序是從上到下遍歷谬泌，然后一列一列向右進(jìn)行（圖中藍(lán)色箭頭，順序是從左往右）逻谦。因此在遍歷到紅色方框的時(shí)候掌实，左上角也是已經(jīng)有值了，因此這種方式也可行邦马。
所以雖然兩種方式的遍歷順序不同贱鼻，但是都滿足dp[i][j]需要的數(shù)據(jù)就是左上角這一需求，所以都可以滋将。 -
舉例推導(dǎo)dp數(shù)組 （打印結(jié)果）
dp數(shù)組結(jié)果
本例最終結(jié)果就如上圖所示邻悬。然后本題在LeetCode沒有原題，所以暫時(shí)不出具體題目耕渴。本篇旨在分析清楚01背包問題的基本底層邏輯拘悦，希望給背包問題打好基礎(chǔ)。背包問題只是基礎(chǔ)橱脸，在LeetCode中需要掌握一些實(shí)際應(yīng)用础米。
（稍后補(bǔ)充例題講解） - - - - -
