文章目錄
- 什麼是01背包問題？
- 二維
- 動态規劃五步走：
- 一維 (滾動數組)
什麼是01背包問題？
有很多種背包 ，完全背包啊機率背包啊，多重背包啥的，但都逃不過01背包，01背包是基礎、
題目大概是這樣的：
有一個小偷，背着書包去偷東西，這個小偷的背包有固定容量，所偷的物品有固定的價值和其對應的重量。
現在問，小偷能偷走東西的最大價值。
二維
老規矩
動态規劃五步走：
确定dp數組以及下标的含義：
dp[i][j] 表示從1到i中任意選擇物品，背包容量為j時的最大價值。這裡選擇物品可以是1件，可以是2件，也可以是i-1件全拿。
可以看下面這個我偷來的圖幫助了解。
2.确定遞推公式：
動态規劃思想都是局部最優，然後一步一步的最優推到最後結果。
細緻化的看這個問題，對于一件物品，隻有兩種可能，小偷選擇偷走，或者不偷。
- 不偷：則背包的容量沒變化，偷走物品的總價值也沒變化，那麼此時dp[i][j] = dp[i-1][j] 。可以看上面那個二維數組的圖，該偷x号物品了，你選擇不偷，那你此時的背包容量和總價值就和上一個物品時的容量和總價值一樣，是以就是dp[i][j] = dp[i-1][j] ，對應上面的圖就是上面的格子移動到下面了，數值沒變。
- 偷：此時背包容量需要減去即将放進來的這件物品的容量，總價值也要加上即将放進來的這件物品的價值，是以dp[i][j] = dp[i-1][j-weight[i]] + value[i],這個遞推公式可以這樣了解，假如現在背包容量為10，即将放進來的物品重量為3，那麼這時候需要找到背包容量為10-3 = 7，時的最大價值，再加上此時的物品的價值，就是新的背包容量10時的最大價值。
是以遞推公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
3.dp數組初始化：
看一下上面的遞推公式，想要得到某個格子的值，要麼由其正上方的格子推過來(不偷的情況)，要麼由左上角的區域推過(偷的情況)。
是以初始化需要最上面一行和最左邊一列。
再看一下我偷的這個圖。
顯然，當背包容量為0的時候，裝不下任何東西，是以最左邊一列都是0。
最上面一行就要判斷物品0的重量了，小于背包容量則填價值，否則填0。
其餘地方初始化什麼都一樣，因為其他的地方都是由上面或者左上推過來的，都會被計算新的值然後覆寫掉。
4.确定周遊順序:
這個其實也無所謂，因為剛才說了除了第一列和第一行之外的地方都是新計算出來的，是以無論先周遊物品還是先周遊背包都可以。
一般情況下都是先周遊物品，再周遊背包。
5.舉例推導dp數組：
這一步其實就是遇到真實題的時候，如果遇到錯誤，可以直接按照推導公式模拟一邊結果，便于debug。
一維 (滾動數組)
一維比二維的難了解感覺。
首先再看一下二維的那張圖
二維變一維，但是for循環依舊是兩層，可以了解成，每次都是一個新的一維數組，也就是每次新的一維數組依賴于上一次的一維數組做覆寫。
看最上面的圖，也就每次都是新的一行，依賴于上一行。
這一點可以從二維的遞推公式中看出來：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
無論是哪一種情況，拿或者不拿，都是依賴于上一行的狀态。
是以着也叫滾動數組，就是一行一行整體往下滾動嘛。
難點：
很多題解在講周遊順序的時候都會說要倒叙周遊，說什麼01背包每件物品隻能拿一次，正序周遊就拿了兩次，巴拉巴拉一堆。
這塊具體為啥要倒叙周遊呢?
首先要明白二維數組的遞推過程，然後才能看懂二維變一維的過程。
假設目前有背包容量為10，可以裝的最大價值， 記為g(10)。
即将進來的物品重量為6。價值為9。
那麼此時可以選擇裝該物品或者不裝該物品。
如果不裝該物品，顯然背包容量無變化，這裡對應二維數組，其實就是取該格子上方的格子複制下來，就是所說的滾動下來，直接g[10] = g[10]，這兩個g[10]要搞清楚，右邊的g[10]是上一輪記錄的，也就是對應二維數組裡上一層的值，而左邊是新的g[10]，也就是對應二維數組裡下一層的值。
如果裝該物品，則背包容量= g(10-6) = g(4) + 9 ，也就是 g(10) = g(4) + 6 ,這裡的6顯然就是新進來的物品的價值，g(10)就是新記錄的，對應二維數組裡下一層的值，而這裡的g(4)是對應二維數組裡上一層的值，通俗的來講：你要找到上一層也就是上一狀态下 背包容量為4時的能裝的最大價值，用它來更新下一層的這一狀态，也就是加入了價值為9的物品的新狀态。
這時候如果是正序周遊會怎麼樣？ g(10) = g(4) + 6 ，這個式子裡的g(4)就不再是上一層的了，因為你是正序啊，g(4) 比g(10)提前更新，那麼此時程式已經沒法讀取到上一層的g(4)了，新更新的下一層的g(4)覆寫掉了，這裡也就是為啥有題解說一件物品被拿了兩次的原因。
周遊的時候先周遊物品，再背包，不能颠倒：
# 先周遊物品, 再周遊背包容量
for i in range(len(weight)):
for j in range(bag_weight, weight[i] - 1, -1):
# 遞歸公式
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]) 參考1
參考2