動(dòng)態(tài)規(guī)劃：關(guān)于01背包問題，你該了解這些！
對(duì)于面試的話，其實(shí)掌握01背包，和完全背包，就夠用了，最多可以再來一個(gè)多重背包。
如果這幾種背包，分不清，我這里畫了一個(gè)圖，如下：
至于背包九講其其他背包，面試幾乎不會(huì)問，都是競(jìng)賽級(jí)別的了，leetcode上連多重背包的題目都沒有，所以題庫(kù)也告訴我們，01背包和完全背包就夠用了。
而完全背包又是也是01背包稍作變化而來，即：完全背包的物品數(shù)量是無(wú)限的。
所以背包問題的理論基礎(chǔ)重中之重是01背包，一定要理解透!
leetcode上沒有純01背包的問題，都是01背包應(yīng)用方面的題目，也就是需要轉(zhuǎn)化為01背包問題。
所以我先通過純01背包問題，把01背包原理講清楚，后續(xù)再講解leetcode題目的時(shí)候，重點(diǎn)就是講解如何轉(zhuǎn)化為01背包問題了。
之前可能有些錄友已經(jīng)可以熟練寫出背包了，但只要把這個(gè)文章仔細(xì)看完，相信你會(huì)意外收獲!
01 背包
有N件物品和一個(gè)最多能被重量為W 的背包。第i件物品的重量是weight[i]，得到的價(jià)值是value[i] 。每件物品只能用一次，求解將哪些物品裝入背包里物品價(jià)值總和最大。
這是標(biāo)準(zhǔn)的背包問題，以至于很多同學(xué)看了這個(gè)自然就會(huì)想到背包，甚至都不知道暴力的解法應(yīng)該怎么解了。
這樣其實(shí)是沒有從底向上去思考，而是習(xí)慣性想到了背包，那么暴力的解法應(yīng)該是怎么樣的呢?
每一件物品其實(shí)只有兩個(gè)狀態(tài)，取或者不取，所以可以使用回溯法搜索出所有的情況，那么時(shí)間復(fù)雜度就是O(2^n)，這里的n表示物品數(shù)量。
所以暴力的解法是指數(shù)級(jí)別的時(shí)間復(fù)雜度。進(jìn)而才需要?jiǎng)討B(tài)規(guī)劃的解法來進(jìn)行優(yōu)化!
在下面的講解中，我舉一個(gè)例子：
背包最大重量為4。
物品為：
| 重量 | 價(jià)值 | |
|---|---|---|
| 物品0 | 1 | 15 |
| 物品1 | 3 | 20 |
| 物品2 | 4 | 30 |
問背包能背的物品最大價(jià)值是多少?
以下講解和圖示中出現(xiàn)的數(shù)字都是以這個(gè)例子為例。
二維dp數(shù)組01背包
依然動(dòng)規(guī)五部曲分析一波。
確定dp數(shù)組以及下標(biāo)的含義
對(duì)于背包問題，有一種寫法， 是使用二維數(shù)組，即dp[i][j] 表示從下標(biāo)為[0-i]的物品里任意取，放進(jìn)容量為j的背包，價(jià)值總和最大是多少。
只看這個(gè)二維數(shù)組的定義，大家一定會(huì)有點(diǎn)懵，看下面這個(gè)圖：
要時(shí)刻記著這個(gè)dp數(shù)組的含義，下面的一些步驟都圍繞這dp數(shù)組的含義進(jìn)行的，如果哪里看懵了，就來回顧一下i代表什么，j又代表什么。
2.確定遞推公式
再回顧一下dp[i][j]的含義：從下標(biāo)為[0-i]的物品里任意取，放進(jìn)容量為j的背包，價(jià)值總和最大是多少。
那么可以有兩個(gè)方向推出來dp[i][j]，
- 由dp[i - 1][j]推出，即背包容量為j，里面不放物品i的最大價(jià)值，此時(shí)dp[i][j]就是dp[i - 1][j]
- 由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 為背包容量為j - weight[i]的時(shí)候不放物品i的最大價(jià)值，那么dp[i - 1][j - weight[i]] + value[i] (物品i的價(jià)值)，就是背包放物品i得到的最大價(jià)值
所以遞歸公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
3.dp數(shù)組如何初始化
關(guān)于初始化，一定要和dp數(shù)組的定義吻合，否則到遞推公式的時(shí)候就會(huì)越來越亂。
首先從dp[i][j]的定義觸發(fā)，如果背包容量j為0的話，即dp[i][0]，無(wú)論是選取哪些物品，背包價(jià)值總和一定為0。如圖：
再看其他情況。
狀態(tài)轉(zhuǎn)移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推導(dǎo)出來，那么i為0的時(shí)候就一定要初始化。
dp[0][j]，即：i為0，存放編號(hào)0的物品的時(shí)候，各個(gè)容量的背包所能存放的最大價(jià)值。
代碼如下：
- // 倒敘遍歷
- for (int j = bagWeight; j >= weight[0]; j--) {
- dp[0][j] = dp[0][j - weight[0]] + value[0]; // 初始化i為0時(shí)候的情況
- }
大家應(yīng)該發(fā)現(xiàn)，這個(gè)初始化為什么是倒敘的遍歷的?正序遍歷就不行么?
正序遍歷還真就不行，dp[0][j]表示容量為j的背包存放物品0時(shí)候的最大價(jià)值，物品0的價(jià)值就是15，因?yàn)轭}目中說了**每個(gè)物品只有一個(gè)!**所以dp[0][j]如果不是初始值的話，就應(yīng)該都是物品0的價(jià)值，也就是15。
但如果一旦正序遍歷了，那么物品0就會(huì)被重復(fù)加入多次!例如代碼如下：
- // 正序遍歷
- for (int j = weight[0]; j <= bagWeight; j++) {
- dp[0][j] = dp[0][j - weight[0]] + value[0];
- }
例如dp[0][1] 是15，到了dp[0][2] = dp[0][2 - 1] + 15; 也就是dp[0][2] = 30 了，那么就是物品0被重復(fù)放入了。
所以一定要倒敘遍歷，保證物品0只被放入一次!這一點(diǎn)對(duì)01背包很重要，后面在講解滾動(dòng)數(shù)組的時(shí)候，還會(huì)用到倒敘遍歷來保證物品使用一次!
此時(shí)dp數(shù)組初始化情況如圖所示：
dp[0][j] 和 dp[i][0] 都已經(jīng)初始化了，那么其他下標(biāo)應(yīng)該初始化多少呢?
dp[i][j]在推導(dǎo)的時(shí)候一定是取價(jià)值最大的數(shù)，如果題目給的價(jià)值都是正整數(shù)那么非0下標(biāo)都初始化為0就可以了，因?yàn)?就是最小的了，不會(huì)影響取最大價(jià)值的結(jié)果。
如果題目給的價(jià)值有負(fù)數(shù)，那么非0下標(biāo)就要初始化為負(fù)無(wú)窮了。例如：一個(gè)物品的價(jià)值是-2，但對(duì)應(yīng)的位置依然初始化為0，那么取最大值的時(shí)候，就會(huì)取0而不是-2了，所以要初始化為負(fù)無(wú)窮。
這樣才能讓dp數(shù)組在遞歸公式的過程中取最大的價(jià)值，而不是被初始值覆蓋了。
最后初始化代碼如下：
- // 初始化 dp
- vector<vector<int>> dp(weight.size() + 1, vector<int>(bagWeight + 1, 0));
- for (int j = bagWeight; j >= weight[0]; j--) {
- dp[0][j] = dp[0][j - weight[0]] + value[0];
- }
費(fèi)了這么大的功夫，才把如何初始化講清楚，相信不少同學(xué)平時(shí)初始化dp數(shù)組是憑感覺來的，但有時(shí)候感覺是不靠譜的。
4.確定遍歷順序
在如下圖中，可以看出，有兩個(gè)遍歷的維度：物品與背包重量
那么問題來了，先遍歷 物品還是先遍歷背包重量呢?
其實(shí)都可以!!但是先遍歷物品更好理解。
那么我先給出先遍歷物品，然后遍歷背包重量的代碼。
- // weight數(shù)組的大小 就是物品個(gè)數(shù)
- for(int i = 1; i < weight.size(); i++) { // 遍歷物品
- for(int j = 0; j <= bagWeight; j++) { // 遍歷背包容量
- if (j < weight[i]) dp[i][j] = dp[i - 1][j]; // 這個(gè)是為了展現(xiàn)dp數(shù)組里元素的變化
- else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
- }
- }
先遍歷背包，再遍歷物品，也是可以的!(注意我這里使用的二維dp數(shù)組)
例如這樣：
- // weight數(shù)組的大小 就是物品個(gè)數(shù)
- for(int j = 0; j <= bagWeight; j++) { // 遍歷背包容量
- for(int i = 1; i < weight.size(); i++) { // 遍歷物品
- if (j < weight[i]) dp[i][j] = dp[i - 1][j];
- else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
- }
- }
為什么也是可以的呢?
要理解遞歸的本質(zhì)和遞推的方向。
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]]推導(dǎo)出來的。
dp[i-1][j]和dp[i - 1][j - weight[i]] 都在dp[i][j]的左上角方向(包括正左和正上兩個(gè)方向)，那么先遍歷物品，再遍歷背包的過程如圖所示：
再來看看先遍歷背包，再遍歷物品呢，如圖：
大家可以看出，雖然兩個(gè)for循環(huán)遍歷的次序不同，但是dp[i][j]所需要的數(shù)據(jù)就是左上角，根本不影響dp[i][j]公式的推導(dǎo)!
但先遍歷物品再遍歷背包這個(gè)順序更好理解。
其實(shí)背包問題里，兩個(gè)for循環(huán)的先后循序是非常有講究的，理解遍歷順序其實(shí)比理解推導(dǎo)公式難多了。
5.舉例推導(dǎo)dp數(shù)組
來看一下對(duì)應(yīng)的dp數(shù)組的數(shù)值，如圖：
最終結(jié)果就是dp[2][4]。
建議大家此時(shí)自己在紙上推導(dǎo)一遍，看看dp數(shù)組里每一個(gè)數(shù)值是不是這樣的。
做動(dòng)態(tài)規(guī)劃的題目，最好的過程就是自己在紙上舉一個(gè)例子把對(duì)應(yīng)的dp數(shù)組的數(shù)值推導(dǎo)一下，然后在動(dòng)手寫代碼!
很多同學(xué)做dp題目，遇到各種問題，然后憑感覺東改改西改改，怎么改都不對(duì)，或者稀里糊涂就改過了。
主要就是自己沒有動(dòng)手推導(dǎo)一下dp數(shù)組的演變過程，如果推導(dǎo)明白了，代碼寫出來就算有問題，只要把dp數(shù)組打印出來，對(duì)比一下和自己推導(dǎo)的有什么差異，很快就可以發(fā)現(xiàn)問題了。
完整C++測(cè)試代碼
- void test_2_wei_bag_problem1() {
- vector<int> weight = {1, 3, 4};
- vector<int> value = {15, 20, 30};
- int bagWeight = 4;
- // 二維數(shù)組
- vector<vector<int>> dp(weight.size() + 1, vector<int>(bagWeight + 1, 0));
- // 初始化
- for (int j = bagWeight; j >= weight[0]; j--) {
- dp[0][j] = dp[0][j - weight[0]] + value[0];
- }
- // weight數(shù)組的大小 就是物品個(gè)數(shù)
- for(int i = 1; i < weight.size(); i++) { // 遍歷物品
- for(int j = 0; j <= bagWeight; j++) { // 遍歷背包容量
- if (j < weight[i]) dp[i][j] = dp[i - 1][j];
- else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
- }
- }
- cout << dp[weight.size() - 1][bagWeight] << endl;
- }
- int main() {
- test_2_wei_bag_problem1();
- }
以上遍歷的過程也可以這么寫：
- // 遍歷過程
- for(int i = 1; i < weight.size(); i++) { // 遍歷物品
- for(int j = 0; j <= bagWeight; j++) { // 遍歷背包容量
- if (j - weight[i] >= 0) {
- dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
- }
- }
- }
這么寫打印出來的dp數(shù)據(jù)這就是這樣：
空出來的0其實(shí)是用不上的，版本一 能把完整的dp數(shù)組打印出來，出來我用版本一來講解。
總結(jié)
講了這么多才剛剛把二維dp的01背包講完，這里大家其實(shí)可以發(fā)現(xiàn)最簡(jiǎn)單的是推導(dǎo)公式了，推導(dǎo)公式估計(jì)看一遍就記下來了，但難就難在如何初始化和遍歷順序上。
可能有的同學(xué)并沒有注意到初始化 和 遍歷順序的重要性，我們后面做力扣上背包面試題目的時(shí)候，大家就會(huì)感受出來了。
本文轉(zhuǎn)載自微信公眾號(hào)「 代碼隨想錄」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系代碼隨想錄公眾號(hào)。
