1. 題目

1.1 題目描述

有件物品和一個容量為的背包。「每件物品只能使用一次」。 第件物品的體積是，價值是。 求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大。

1.2 經(jīng)典例題

洛谷P1048 [NOIP2005 普及組] 采藥

2. 思路

2.1 基本思路

這是最基礎(chǔ)的背包問題，特點是：「每種物品僅有一件，可以選擇取或不取」。 考慮如何將問題轉(zhuǎn)化成規(guī)模更小的子問題。對于第件物品，在最終方案中要么不取、要么取，于是我們可以對這兩種情況進行分類討論，轉(zhuǎn)化為子問題：

• 如果不取第件物品，那么相當(dāng)于只有前件物品、背包大小相同的子問題

• 如果取了第件物品，那么相當(dāng)于只有前件物品（件物品已經(jīng)經(jīng)過了選擇）、背包大小減去的子問題，在它的答案上再加上的價值（取了第件物品貢獻的價值）。

在這兩種情況中取價值更高的，作為答案。

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

設(shè)表示使用編號為的物品，背包容量為時的最大價值，有轉(zhuǎn)移方程：

2.3 例子

為了加深對狀態(tài)轉(zhuǎn)移方程的理解，我們來看下圖的一個例子，每個格子代表一個狀態(tài)，代表初始狀態(tài)，藍(lán)色的格子代表已經(jīng)求得的狀態(tài)，灰色的格子代表非法狀態(tài)，紅色的格子代表當(dāng)前正在進行轉(zhuǎn)移的狀態(tài)，圖中的第行代表了前個物品對應(yīng)容量的最優(yōu)值，第個物品的體積為，價值為，則有狀態(tài)轉(zhuǎn)移如下：

2.4 代碼

for?(int?i?=?1;?i?<=?n;?i++)?{??//?遍歷物品
????for?(int?j?=?0;?j?<=?W;?j++)?{??//?遍歷背包容量
????????if?(j?<?w[i])?dp[i][j]?=?dp[i-1][j];
????????else?dp[i][j]?=?max(dp[i-1][j],?dp[i-1][j-w[i]]?+?v[i])
????}
}


3. 優(yōu)化空間復(fù)雜度

我們發(fā)現(xiàn)以上方法的狀態(tài)數(shù)是的，整個求解過程的時間和空間復(fù)雜度均為，其中時間復(fù)雜度已經(jīng)不能再優(yōu)化了，但是空間復(fù)雜度還是可以優(yōu)化的。

3.1 滾動數(shù)組

我們觀察剛才的代碼：每個在轉(zhuǎn)移時只用到了，即上一行的數(shù)據(jù)。也就是說，比更小的再也不會被用到。如果把看成一張二維的表格，那么只有兩行的格子是 “活躍” 的?；谶@一思想，我們可以只保存這兩行。

3.2 代碼

int?pre?=?0,?cur?=?1;??//?pre:前一行??cur:當(dāng)前行
for?(int?i?=?1;?i?<=?n;?i++)?{
????for?(int?j?=?0;?j?<=?W;?j++)?{
????????if?(j?<?w[i])?dp[cur][j]?=?dp[pre][j];
????????else?dp[cur][j]?=?max(dp[pre][j],?dp[pre][j-w[i]]?+?v[i])
????}
????swap(pre,?cur);??//?每一輪結(jié)束?當(dāng)前行變成前一行,?交換,?每次只用兩行的空間
}


3.3 一維數(shù)組

我們繼續(xù)剛才的思路：把看成一張二維的表格，那么每個格子在轉(zhuǎn)移時，只會用到上一行中在它左側(cè)的格子。如果我們調(diào)整一下轉(zhuǎn)移的順序，每一行從右往左進行更新（從大到?。敲?「“活躍”」 的格子就正好只有「上一行的左半部分以及這一行的右半部分」。（即除白色格子以外的格子）

那么實際上我們只需要保存這些 “活躍” 格子的狀態(tài)就可以了，我們可以得到一維的狀態(tài)轉(zhuǎn)移方程：

3.4 代碼

for?(int?i?=?1;?i?<=?n;?i++)?{??//?遍歷物品
????for?(int?j?=?W;?j?>=?w[i];?j--)?{??//?遍歷背包容量
????????dp[j]?=?max(dp[j],?dp[j-w[i]]?+?v[i]);
????}
}


3.5 例子

我們通過下面這個例子來深入理解下，為什么降維之后，遍歷背包容量（內(nèi)層循環(huán)）要「逆序遍歷」。 假定目前背包容量為，有以下三個物品：

求將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大。

「我們先來看內(nèi)層循環(huán)」「從小到大遍歷（順序遍歷）的情況」：

背包基本要求是「每件物品只能使用一次」，我們從使用第一件物品的時候，就可以發(fā)現(xiàn)如果內(nèi)層循環(huán)從小到大遍歷，那么這件物品會被多次使用。
比如的狀態(tài)一定來自，而的狀態(tài)來自于，這時候我們發(fā)現(xiàn)體積為的第一件物品被用了兩次：

「接下來我們來看下內(nèi)層循環(huán)」「從大到小遍歷（逆序遍歷）的情況」：

上面「逆序遍歷」的是不是就實現(xiàn)了每件物品只使用一次的要求，其實「順序遍歷」 每件物品可以被反復(fù)使用，這個就是我們后面要講的完全背包。

4. 經(jīng)典題型

4.1 最大值問題

「題目鏈接」：洛谷P1048 [NOIP2005 普及組] 采藥
「題意」：有件物品和一個容量為的背包。「每件物品只能使用一次。」第件物品的體積是，價值是。求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大。
「題解」：模板題，見上文

4.2 最小值問題

「題目鏈接」：洛谷P1049 [NOIP2001 普及組] 裝箱問題
「題意」：有一個箱子容量為，同時有個物品，每個物品有一個體積。
現(xiàn)在從個物品中，任取若干個裝入箱內(nèi)（也可以不取），使箱子的剩余空間最小。輸出這個最小值。
「題解」：本題可以認(rèn)為每個物品的價值就是體積，: 在的箱子容量下能夠裝入的最大總體積。 題目要求最少剩余空間，那么我們最后答案就是。 對于這種最小值問題，我們轉(zhuǎn)化下思路，用總值減去求得的最大值，即是最小值。
「擴展題目」：有件物品，第件物品價值為，現(xiàn)在要把這些物品分成兩堆，期望兩堆的價值之差最小，求最小價值差。（原理本質(zhì)來說是一樣的，我們先用求出所有物品價值之和，然后求出，即盡可能接近總價值一半的情況，最后答案就是）。

4.3 存在性問題

「題目鏈接」：洛谷P1877 [HAOI2012] 音量調(diào)節(jié)
「題意」：給定首歌和剛開始的音量，每首歌開始前能夠改變的音量是(當(dāng)前音量調(diào)高或者調(diào)低)，音量不能小于且不能大于。求首歌演唱完之后，最大音量是多少。
「題解」：存在性問題本質(zhì)來說就是在背包基礎(chǔ)上，用表示能夠達(dá)到這個狀態(tài)，表示不能夠達(dá)到這個狀態(tài)。
在本題中表示能否達(dá)到這個音量，一開始我們把數(shù)組初始化成，表示所有音量都無法達(dá)到，然后把題目中給定的初始音量標(biāo)記成，即。

在每首歌開始前，我們可以在當(dāng)前音量的基礎(chǔ)上增加或減少，那么我們是不是就可以去檢測一下或是否在之前達(dá)到過，如果達(dá)到過我們就能在之前的狀態(tài)基礎(chǔ)上，增加或者減少，達(dá)到這個音量。
「細(xì)節(jié)問題」：本題無法用一維數(shù)組優(yōu)化空間復(fù)雜度的形式（但是滾動數(shù)組還是可以的），問題在于我們內(nèi)層循環(huán)「逆序遍歷」的過程中，會影響到，使得該次改變執(zhí)行了多次（即背包中該件物品反復(fù)使用），和上文講到的內(nèi)層循環(huán)「順序遍歷」，會影響到，使得該件物品反復(fù)使用，原理一樣。
「練習(xí)題目」：洛谷P8742 [藍(lán)橋杯 2021 省A] 砝碼稱重

4.4 二維費用問題

「題目鏈接」：洛谷P1794 裝備運輸
「題意」：有件物品和一個可容納體積、承載重量的背包。「每件物品只能使用一次。」第件物品的體積是，重量是，價值是。求解將哪些物品裝入背包，可使得這些物品的總體積不超過背包的可容納體積、總重量不超過背包的可承載重量，且總價值最大。
「題解」：經(jīng)典背包的費用只有體積，二維費用問題是在原來問題的基礎(chǔ)上多加了一維費用，那對應(yīng)的我們只需要給狀態(tài)也多加一維就好了。為了保證每件物品只使用一次，對于體積和重量的這兩維，我們都采用逆序的循環(huán)。對應(yīng)的狀態(tài)轉(zhuǎn)移方程：
「代碼」：

for?(int?i?=?1;?i?<=?n;?i++)
for?(int?j?=?V;?j?>=?v[i];?j--)
for?(int?k?=?G;?k?>=?g[i];?k--)
dp[j][k]?=?max(dp[j][k],?dp[j?-?v[i]][k?-?g[i]]?+?t[i]);


「練習(xí)題目」：洛谷P1507 NASA的食物計劃

4.5 方案數(shù)問題

「題目鏈接」：AcWing 背包問題求方案數(shù)
「題意」：有件物品和一個容量為的背包。「每件物品只能使用一次?！?/strong>第件物品的體積是，價值是。求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大。 輸出「最優(yōu)選法的方案數(shù)」。注意答案可能很大，請輸出答案模的結(jié)果。
「題解」：對于求解方案數(shù)的問題，主要在于轉(zhuǎn)移方程的時候不再是、，或者像存在性問題進行標(biāo)記，而是說我們需要把之前狀態(tài)的方案數(shù)加到當(dāng)前狀態(tài)上，即，具體我們看下這個例題。
本題求在最優(yōu)選法情況下的方案數(shù)。那么我們在原來求最優(yōu)選法背包的基礎(chǔ)上，可以再定義一個數(shù)組，表示在的背包大小下最優(yōu)選法的方案數(shù)。那么數(shù)組會受到數(shù)組（或者說最優(yōu)選法）的影響。有以下兩種情況：

• 當(dāng)，即在背包大小為，在使用第個物品的時候出現(xiàn)了一個新的最優(yōu)值，那么顯然我們需要更新下。同時我們要讓，因為這時候出現(xiàn)了新的最優(yōu)選法，原來的就沒用了，我們拿當(dāng)前轉(zhuǎn)移過來的方案數(shù)即賦值。

• 當(dāng)，即在背包大小為，在使用第個物品的時候出現(xiàn)了一個一樣的最優(yōu)值情況，那么我們這時候只需要給加上這種情況的方案，即

普通的求方案數(shù)問題只需要轉(zhuǎn)移就可以了，比如練習(xí)題目中的 「小A點菜」，把之前所有能夠轉(zhuǎn)移到當(dāng)前狀態(tài)的前置狀態(tài)的方案數(shù)都加上。但是加上了最優(yōu)之類的條件，我們就需要考慮當(dāng)前狀態(tài)的轉(zhuǎn)移是「更優(yōu)的情況」還是「一樣優(yōu)的情況，」根據(jù)不同情況對方案計數(shù)進行更改。
同樣的思想在圖論的最短路（松弛操作）、拓?fù)渑判蛑愃惴▎栴}中也經(jīng)常出現(xiàn)。
「細(xì)節(jié)問題」：本題需要考慮把先全部初始化成，因為背包什么都不裝也是一種方案。
「代碼」：

for?(int?i?=?1;?i?<=?N;?i++)
????for?(int?j?=?V;?j?>=?v[i];?j--)?{
????????if?(dp[j]?<?dp[j?-?v[i]]?+?w[i])?{
????????????dp[j]?=?dp[j?-?v[i]]?+?w[i];
????????????cnt[j]?=?cnt[j?-?v[i]]?%?mod;
????????}
????????else?if?(dp[j]?==?dp[j?-?v[i]]?+?w[i])?{
????????????cnt[j]?=?(cnt[j]?+?cnt[j?-?v[i]])?%?mod;
????????}
????}


「練習(xí)題目」：洛谷P1164 小A點菜

4.6 輸出具體方案問題

「題目鏈接」：AcWing背包問題求具體方案
「題意」：有件物品和一個容量為的背包。「每件物品只能使用一次。」第件物品的體積是，價值是。求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大。輸出「字典序最小的方案」。
「題解」：輸出具體方案本質(zhì)來說就是輸出轉(zhuǎn)移路徑。假設(shè)最優(yōu)解是，那么我們判斷第個物品是否選擇，實際上就是看是從哪個狀態(tài)轉(zhuǎn)移過來的：

• 如果，即不選第個物品。

• 如果，那么是選了這個物品，得到最優(yōu)解。

「細(xì)節(jié)問題」：題目中要輸出字典序最小的方案，我們物品得逆序遍歷，因為從順序遍歷時，如果序號和序號的最大價值都是，那么最后記錄的最大值對應(yīng)的序號就是，后面的會給前面的覆蓋掉，我們實際想要的是序號。
「代碼」：

for?(int?i?=?N;?i?>=?1;?i--)?{
?for?(int?j?=?1;?j?<=?W;?j++)?{
??if?(j?>=?w[i])?dp[i][j]?=?max(dp[i+1][j],?dp[i+1][j-w[i]]?+?v[i]);
??else?dp[i][j]?=?dp[i+1][j];
?}
}

for?(int?i?=?1;?i?<=?N;?i++)?{
?if?(W?>=?w[i]?&&?dp[i][W]?==?dp[i+1][W-w[i]]?+?v[i])?{
??ans.push_back(i);
??W?-=?w[i];
?}
}


「擴展題目（大容量背包）」：有件物品和一個容量為的背包。「每件物品只能使用一次?！?/strong>第件物品的體積是。求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，求最大總體積是多少？具體方案是怎么樣的？
（）「題解」：對于這種大容量背包，很明顯開二維會炸空間。我們需要給它優(yōu)化一下，給它降下維。有一種方式是可以用二進制bitset優(yōu)化（這個不細(xì)說了，有興趣的可以自己研究下）。我這里介紹下類似搜索中記錄路徑的方式，我們可以用去記錄下在這個背包大小情況用了這個物品。最后倒序去遍歷檢測一下第物品是否需要被選（和上面小容量那題一樣），并且是否記錄在這個里。

for?(int?i?=?1;?i?<=?n;?i++)?{
????for?(int?j?=?W;?j?>=?w[i];?j--)?{
????????if?(dp[j-w[i]]?+?w[i]?>?dp[j])?{
????????????dp[j]?=?dp[j-w[i]]?+?w[i];
????????????path[j]?=?i;
????????}
????}
}


for?(int?i?=?n;?i?>=?1;?i--)?{
????if?(W?>=?w[i]&&?dp[W]?==?dp[W-w[i]]?+?w[i]?&&?path[W]?==?i)?{
????????ans.push_back(i);
????????W?-=?w[i];
????}
}


標(biāo)簽：