前言

又是一次漫長的更新（我真不是故意的aaaaaaaaaaaaaaa），先不多說了，直接給我~坐下~說錯了說錯了，直接開始~

背包問題----動態(tài)規(guī)劃

背包問題（knapsack problem）

動態(tài)規(guī)劃（dynamic programming）

01背包：可行性

對一個背包最多載重m斤，共有n件物品，第i件物品重量為w[i]。對每件物品可選擇拿走或不拿。請問能否恰好拿到總重量為m斤？

?

?01決策：不選0，選1

湊數(shù)：可行性

目標(biāo)湊出數(shù)字m，有n個數(shù)字可以使用，第i個數(shù)字為x[i]。對每一個數(shù)字最多可以選用1次。請問能否恰好湊出數(shù)字m？

?01決策：不選0，選1

簡化問題

01背包：可行性

f[i][j]表示只用前i個數(shù)字能否湊出j

初始條件?

f[0][0]=1

狀態(tài)轉(zhuǎn)移方程

若j<x[i]——f[i][j]=f[i-1][j]

若j>=x[i]——f[i][j]=f[i-1][j]或f[i-1][j-x[i]]

01背包：3種問題

可行性判定問題

用n個物品能否恰好湊出m斤重量

方案計數(shù)問題

用n個物品能否恰好湊出m斤各種方案

最優(yōu)化問題

用n個物品湊出不超過m斤時最多幾斤

01背包

關(guān)于01背包，建議結(jié)合我的B站視頻一起學(xué)習(xí)，相信會對你徹底理解背包問題有很大幫助！

帶你學(xué)透0-1背包問題！| 關(guān)于背包問題，你不清楚的地方，這里都講了！| 動態(tài)規(guī)劃經(jīng)典問題 | 數(shù)據(jù)結(jié)構(gòu)與算法_嗶哩嗶哩_bilibili?www.bilibili.com/video/BV1cg411g7Y6?編輯https://link.zhihu.com/?target=https%3A//www.bilibili.com/video/BV1cg411g7Y6帶你學(xué)透01背包問題（滾動數(shù)組篇） | 從此對背包問題不再迷茫！_嗶哩嗶哩_bilibili?www.bilibili.com/video/BV1BU4y177kY?編輯https://link.zhihu.com/?target=https%3A//www.bilibili.com/video/BV1BU4y177kY

有N件物品和一個最多能被重量為W 的背包。第i件物品的重量是weight[i]，得到的價值是value[i] 。每件物品只能用一次，求解將哪些物品裝入背包里物品價值總和最大。

?

這是標(biāo)準(zhǔn)的背包問題，以至于很多混絲看了這個自然就會想到背包，甚至都不知道暴力的解法應(yīng)該怎么解了。

這樣其實是沒有從底向上去思考，而是習(xí)慣性想到了背包，那么暴力的解法應(yīng)該是怎么樣的呢？

每一件物品其實只有兩個狀態(tài)，取或者不取，所以可以使用回溯法搜索出所有的情況，那么時間復(fù)雜度就是O(2^n)，這里的n表示物品數(shù)量。

?二維dp數(shù)組01背包

確定dp數(shù)組以及下標(biāo)的含義

對于背包問題，有一種寫法， 是使用二維數(shù)組，即dp[i][j] 表示從下標(biāo)為[0-i]的物品里任意取，放進(jìn)容量為j的背包，價值總和最大是多少？

要時刻記著這個dp數(shù)組的含義，下面的一些步驟都圍繞這dp數(shù)組的含義進(jìn)行的，如果哪里看懵了，就來回顧一下i代表什么，j又代表什么。

確定遞推公式

再回顧一下dp[i][j]的含義：從下標(biāo)為[0-i]的物品里任意取，放進(jìn)容量為j的背包，價值總和最大是多少。

那么可以有兩個方向推出來dp[i][j]，

• 由dp[i - 1][j]推出，即背包容量為j，里面不放物品i的最大價值，此時dp[i][j]就是dp[i - 1][j]
• 由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 為背包容量為j - weight[i]的時候不放物品i的最大價值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的價值），就是背包放物品i得到的最大價值

所以遞歸公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

dp數(shù)組如何初始化

關(guān)于初始化，一定要和dp數(shù)組的定義吻合，否則到遞推公式的時候就會越來越亂。

首先從dp[i][j]的定義出發(fā)，如果背包容量j為0的話，即dp[i][0]，無論是選取哪些物品，背包價值總和一定為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的時候就一定要初始化。

dp[0][j]，即：i為0，存放編號0的物品的時候，各個容量的背包所能存放的最大價值。

代碼如下：

for (int j = weight[0]; j <= bagWeight; j++) {dp[0][j] = value[0];
}

dp[0][j] 和 dp[i][0] 都已經(jīng)初始化了，那么其他下標(biāo)應(yīng)該初始化多少呢？

dp[i][j]在推導(dǎo)的時候一定是取價值最大的數(shù)，如果題目給的價值都是正整數(shù)那么非0下標(biāo)都初始化為0就可以了，因為0就是最小的了，不會影響取最大價值的結(jié)果。

如果題目給的價值有負(fù)數(shù)，那么非0下標(biāo)就要初始化為負(fù)無窮了。例如：一個物品的價值是-2，但對應(yīng)的位置依然初始化為0，那么取最大值的時候，就會取0而不是-2了，所以要初始化為負(fù)無窮。

而背包問題的物品價值都是正整數(shù)，所以初始化為0，就可以了。

這樣才能讓dp數(shù)組在遞歸公式的過程中取最大的價值，而不是被初始值覆蓋了。

最后初始化代碼如下：

vector<vector<int>> dp(weight.size() + 1, vector<int>(bagWeight + 1, 0));
for (int j = weight[0]; j <= bagWeight; j++) {dp[0][j] = value[0];
}

?那么問題來了，先遍歷物品還是先遍歷背包重量呢？

其實都可以！！ 但是先遍歷物品更好理解。

那么我先給出先遍歷物品，然后遍歷背包重量的代碼。

// weight數(shù)組的大小 就是物品個數(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]; // 這個是為了展現(xiàn)dp數(shù)組里元素的變化else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}
}

?先遍歷背包，再遍歷物品，也是可以的

例如這樣：

// weight數(shù)組的大小 就是物品個數(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]的左上角方向（包括正左和正上兩個方向）

其實背包問題里，兩個for循環(huán)的先后循序是非常有講究的，理解遍歷順序其實比理解推導(dǎo)公式難多了。

總結(jié)

講了這么多才剛剛把二維dp的01背包講完，這里大家其實可以發(fā)現(xiàn)最簡單的是推導(dǎo)公式了，推導(dǎo)公式估計看一遍就記下來了，但難就難在如何初始化和遍歷順序上。

可能有的混絲并沒有注意到初始化和遍歷順序的重要性，我們后面做力扣上背包面試題目的時候，大家就會感受出來了。

（這真是n年一度的大更新）