數據結構與算法學習筆記----動態規劃·背包模型(一)

@@ author: 明月清了個風
@@ first publish time: 2025.5.1

ps??背包模型是動態規劃中的重要模型，基礎課中已對背包模型的幾種模版題有了講解，[鏈接在這](數據結構與算法學習筆記----背包問題_有 n 件物品和一個體積為 m 的背包。第 i 個物品的體積為 vi,價值為 wi。每件物品-CSDN博客)，

??題目非常多，計劃大概寫兩到三篇，建議首先復習一下基礎課中對應的背包模型。這次是按照題目順序寫的，沒有按照視頻講的順序，因為剛開始講的就是一系列多重背包問題，相對比較難，因此沒有按照這個順序。并且按照對應的背包模型進行了題目的分類，沒有完全按照原來的順序。

這一篇中主要是01背包問題和二維背包問題的應用題。

很多題目的代碼都可以進行優化，有些題目給出了優化前后的代碼，有些比較簡單直接給了優化后的如二維背包問題的優化，建議可以先嘗試寫無優化的再看優化后的代碼。

Acwing 423. 采藥

辰辰是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫師。

為此，他想拜附近最有威望的醫師為師。

醫師為了判斷他的資質，給他出了一個難題。

醫師把他帶到一個到處都是草藥的山洞里對他說：“孩子，這個山洞里有一些不同的草藥，采每一株都需要一些時間，每一株也有它自身的價值。我會給你一段時間，在這段時間里，你可以采到一些草藥。如果你是一個聰明的孩子，你應該可以讓采到的草藥的總價值最大。”

如果你是辰辰，你能完成這個任務嗎？

輸入格式

輸入文件的第一行有兩個整數$T$和$M$，用一個空格隔開，$T$代表總共能夠用來采藥的事件，$M$代表山洞里的草藥的數目。

接下來的$M$行每行包括兩個在$1$到$100$之間的整數，分別表示采摘某株草藥的時間和這株草藥的價值。

輸出格式

輸出文件包括一行，這一行只包含一個整數，表示在規定的時間內，可以采到的草藥的最大總價值。

數據范圍

$1\le T\le 1000$，

$0\le M\le 100$

思路

這一題就是01背包問題的包裝版本，思路完全一致，只是加入了具體場景的引用，算是本節內容的入門題了，就不具體講了。可以用來復習01背包，下面給出了兩個版本的代碼，對應了無優化和有優化的版本，主要是對存儲空間進行了優化，優化方法在基礎課中已經詳細講過，這里就不講了，那篇[鏈接在這](數據結構與算法學習筆記----背包問題_有 n 件物品和一個體積為 m 的背包。第 i 個物品的體積為 vi,價值為 wi。每件物品-CSDN博客)。

代碼-無優化

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>using namespace std;const int N = 110, M = 1010;int n, m;
int v[N], w[N];
int f[N][M];int main()
{cin >> m >> n;for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];for(int i = 1; i <= n; i ++){for(int j = 1; j <= m; j ++){f[i][j] = f[i - 1][j];if(j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);}}cout << f[n][m] << endl;return 0;
}

代碼-有優化

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>using namespace std;const int N = 110, M = 1010;int n, m;
int v[N], w[N];
int f[M];int main()
{cin >> m >> n;for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];for(int i = 1; i <= n; i ++){for(int j = m; j >= v[i]; j --)f[j] = max(f[j], f[j - v[i]] + w[i]);}cout << f[m] << endl;return 0;
}

Acwing 1024. 裝箱問題

有一個箱子容量$V$，同時有$n$個物品，每個物品有一個體積(正整數)。

要求$n$個物品中，任取若干個裝入箱內，使箱子的剩余空間為最小。

輸入格式

第一行是一個整數$V$，表示箱子容量。

第二行是一個整數$n$，表示物品數。

接下來$n$行，每行一個正整數，分別表示這$n$個物品的各自體積。

輸出格式

一個整數，表示箱子剩余空間。

數據范圍

$1\le V\le 20000$，

$0\le n\le 30$

思路

這一題也是基本的01背包問題，為使剩余空間最小，就要拿體積做大的組合，雖然沒有物品價值，但是可以將物品價值看成與該物品體積相同，這樣就能轉化為最基本的01背包問題了。

代碼

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>using namespace std;const int N = 20010;int f[N];
int m, n;int main()
{cin >> m >> n;for(int i = 0; i < n; i ++){int v;cin >> v;for(int j = m; j >= v; j --) f[j] = max(f[j], f[j -v] + v);}cout << m - f[m] << endl;return 0;
}

Acwing 278. 數字組合

給定$N$個正整數$A_1,A_2,?,A_N$，從中選出若干個數，使它們的和為$M$，求有多少種方案。

輸入格式

第一行包含兩個整數$N$和$M$。

第二行包含$N$個整數，表示$A_1,A_2,?,A_N$。

輸出格式

包含一個整數，表示可選方案數。

數據范圍

$1\le N<100$，

$1\le M<10000$

$1\le A_i\le 1000$

思路

同樣是01背包的一個應用題，將所有數看成物品，數值看做體積即可，只不過要求的是體積正好為$M$的方案數，對于狀態表示使用f[i][j]表示從前$i$個數中選，且和為$j$的方案，屬性是方案數。

對于狀態轉移，根據第$i$個數的選擇情況即可。

需要注意的是，因為要求的是方案數，因此需要對f[0]進行初始化。

代碼

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>using namespace std;const int N = 10010;int n, m;
int f[N];int main()
{cin >> n >> m;f[0] = 1;for(int i = 1; i <= n; i ++){int v;cin >> v;for(int j = m; j >= v; j --) f[j] += f[j - v];}cout << f[m] << endl;return 0;
}

Acwing 8. 二維費用的背包問題

有$N$件物品和一個容量為$V$的背包，背包能承受的最大重量是$M$。

每件物品只能用一次。體積是$v_i$，重量是$m_i$，價值是$w_i$。

求解將哪些物品裝入背包，可使物品總體積不超過背包容量，總重量不超過背包可承受的最大重量，且價值總和最大。
輸出最大價值。

輸入格式

第一行三個整數，$N,V,M$，用空格隔開，分別表示物品件數、背包容積和背包可承受的最大重量。

接下來$N$行，每行三個整數$v_i,m_i,w_i$，用空格隔開，分別表示第$i$件物品的體積，重量和價值。

輸出格式

輸出一個整數，表示最大價值。

數據范圍

$0<N<1000$，

$0<V,M<100$

$0<v_i,m_i<100$

$0<w_i\le 1000$

思路

對于二維費用來說，僅僅是對一維01背包的擴展，在難度上其實并沒有太大的提升，因為多了一維限制，因此狀態表示也變成了三維，使用f[i][j][k]表示所有從前$i$個物品中選，并且總體積不超過$j$，總重量不超過$k$的選法。

對于狀態劃分，同樣根據最后一個物品的選擇進行劃分，分為選物品$i$和不選物品$i$的兩個部分，代碼很簡單，同樣可以和01背包一樣進行空間優化，這里直接給出了優化版本的代碼，可以先嘗試寫無優化的版本再看這個。

代碼

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>using namespace std;const int N = 1010;int n, V1, V2;
int f[N][N];int main()
{cin >> n >> V1 >> V2;for(int i = 1; i <= n; i ++){int v1,v2,w;cin >> v1 >> v2 >> w;for(int j = V1; j >= v1; j --)for(int k = V2; k >= v2; k --)f[j][k] = max(f[j][k], f[j - v1][k - v2] + w);}cout << f[V1][V2] << endl;return 0;
}

Acwing 1022. 寵物小精靈之收服

寵物小精靈是一部講述小智和他的搭檔皮卡丘一起冒險的故事。

一天，小智和皮卡丘來到了小精靈狩獵場，里面有很多珍貴的野生寵物小精靈。

小智也想收服其中的一些小精靈。然而，野生的小精靈并不那么容易被收服。

對于每一個野生小精靈而言，小智可能需要使用很多個精靈球才能收服它，而在收服過程中，野生小精靈也會對皮卡丘造成一定的傷害（從而減少皮卡丘的體力）。

當皮卡丘的體力小于等于0時，小智就必須結束狩獵（因為他需要給皮卡丘療傷），而使得皮卡丘體力小于等于0的野生小精靈也不會被小智收服。當小智的精靈球用完時，狩獵也宣告結束。

我們假設小智遇到野生小精靈時有兩個選擇：收服它，或者離開它。如果小智選擇了收服，那么一定會扔出能夠收服該小精靈的精靈球，而皮卡丘也一定會受到相應的傷害；如果選擇離開它，那么小智不會損失精靈球，皮卡丘也不會損失體力。

小智的目標有兩個：主要目標是收服盡可能多的野生小精靈；如果可以收服的小精靈數量一樣，小智希望皮卡丘受到的傷害越小（剩余體力越大），因為他們還要繼續冒險。

現在已知小智的精靈球數量和皮卡丘的初始體力，已知每一個小精靈需要的用于收服的精靈球數目和它在被收服過程中會對皮卡丘造成的傷害數目。請問，小智該如何選擇收服哪些小精靈以達到他的目標呢？

輸入格式

輸入數據的第一行包含三個整數：$N$，$M$，$K$，分別代表小智的精靈球數量、皮卡丘初始的體力值、野生小精靈的數量。

之后的$K$行，每一行代表一個野生小精靈，包括兩個整數：收服該小精靈需要的精靈球的數量，以及收服過程中對皮卡丘造成的傷害。

輸出格式

輸出為一行，包含兩個整數$C,R$，分別表示最多收服$C$個小精靈，以及收服$C$個小精靈時皮卡丘的剩余體力值最多為$R$。

數據范圍

$0<N<1000$，

$0<M<500$

$0<K<100$

思路

根據題意可以發現，一共有兩個值有上限，也就是01背包問題中的體積，一個是精靈球的數量，另一個是皮卡丘的體力值，而要求的目標是野生小精靈的數量，因此，這一題為二維背包問題。

對于狀態表示而言，使用f[i][j][k]表示所有從前$i$個物品中選擇，且花費不超過$j$和不超過$k$的選法，也就是有兩個限制，在這一題中就是從前$i$個小精靈中選擇要收服的小精靈，且精靈球數量不能超過$j$，皮卡丘的體力值不能超過$k$的方案，屬性為最大值。

對于狀態轉移而言就和一維背包問題是一樣的。需要注意的是本題的第二問要皮卡丘的剩余體力值最多，需要找到收服$C$個小精靈時剩余的最多體力。

代碼

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>using namespace std;const int N = 1010, M = 510;int n, m, k;
int f[N][M];int main()
{cin >> n >> m >> k;for(int i = 0; i < k; i ++){int v1, v2;cin >> v1 >> v2;for(int j = n; j >= v1; j --)for(int z = m - 1; z >= v2; z --)f[j][z] = max(f[j][z], f[j - v1][z - v2] + 1);}cout << f[n][m - 1] << endl;int x = m - 1;while(x > 0 && f[n][x - 1] == f[n][m - 1]) x --;cout << m - x << endl;return 0;}

Acwing 1020. 潛水員

潛水員為了潛水要使用特殊的裝備。

他有一個帶2種氣體的氣缸：一個為氧氣，一個為氮氣。讓潛水員下潛的深度需要各種的數量的氧和氮。

潛水員有一定數量的氣缸。

每個氣缸都有重量和氣體容量。

潛水員為了完成他的工作需要特定數量的氧和氮。

他完成工作所需氣缸的總重的最低限度的是多少？

例如：潛水員有5個氣缸。每行三個數字為：氧，氮的（升）量和氣缸的重量：

3 36 120
10 25 129
5 50 250
1 45 130
4 20 119

如果潛水員需要5升的氧和60升的氮則總重最小為249（1，2或者4，5號氣缸）。

你的任務就是計算潛水員為了完成他的工作需要的氣缸的重量的最低值。

輸入格式

第一行有$2$個整數$m,n$，他們表示氧、氮各自需要的量。

第二行為整數$k$表示氣缸的個數。

此后的$k$行，每行包括$a_i,b_i,c_i$，$3$個整數，這些各自是：第$i$個氣缸里的氧和氮的容量及汽缸重量。

輸出格式

僅一行包含一個整數，為潛水員完成工作所需的氣缸的重量總和的最低值。

數據范圍

$1\le m\le 21$，

$1\le n\le 79$

$1\le k\le 1000$

$1\le a_i\le 21$

$1\le b_i\le 79$

$1\le c_i\le 800$

思路

首先很容易看出這題有兩個限制氧氣和氮氣，但是與上一題不同的是，對于這兩維費用的要求是至少需要這么多，使重量最低，也就是和上面的題目是反過來的，因此也需要有一些變化。

對于背包問題的狀態表示而言，體積的限制有三種：①體積最多是$j$ ②體積恰好是$j$ ③體積至少是$j$。這一題就是第三種情況。

對于狀態表示，仍然是使用f[i][j][k]，但含義變為所有從前$i$個氣缸中選，并且氧氣至少是$j$，氮氣至少是$k$的選法，要求的屬性是最小值。

對于狀態劃分，仍然是根據第$i$個氣缸的選擇進行劃分，也就是是否包含該氣缸，所有不包含第$i$個物品的所有選法也就是f[i - 1][j][k]，包含第$i$個物品的選擇集合可以先將物品$i$去掉，那么根據一般的表示就是f[i - 1][j - v1][k - v2]，但是需要注意的是，在之前如果是這個式子，因為要求是體積恰好是$j$和$k$，因此我們會有一個判斷就是$j\ge v1$且$k\ge v2$才能成立，但是在這里因為要求是至少有那么多，只要比它多就是成立的，因此對于$j$和$k$的限制就失效了，即使此時$j<v1$或者$k<v2$也可以，因為實際意義是至少要這么多氧氣和氮氣，因此它最低就是$0$，表示什么都沒選，而選擇了物品$i$之后就滿足了氧氣至少為$j$，氮氣至少為$k$，也就是只要比$j$和$k$多就行，多多少都沒事。

代碼

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>using namespace std;const int N = 22, M = 80;int n, m, k;
int f[N][M];int main()
{cin >> n >> m >> k;memset(f, 0x3f, sizeof f);f[0][0] = 0;while(k --){int v1, v2, w;cin >> v1 >> v2 >> w;for(int j = n; j >= 0; j --)for(int z = m; z >= 0; z --)f[j][z] = min(f[j][z], f[max(0, j -v1)][max(0, z - v2)] + w);}cout << f[n][m] << endl;return 0;
}