概述

AcWing 2：

有?N?件物品和一個容量是?V?的背包。每件物品只能使用一次。

第?i?件物品的體積是?v[i]，價值是?w[i]。

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

輸入格式

第一行兩個整數，N，V，用空格隔開，分別表示物品數量和背包容積。

接下來有?N?行，每行兩個整數用空格隔開，分別表示第?i 件物品的體積和價值。

輸出格式

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

數據范圍

0<N,V≤10000<N,V≤1000
0<vi,wi≤10000<vi,wi≤1000

輸入樣例

4 5
1 2
2 4
3 4
4 5

輸出樣例：

8

背包DP是非常經典的動態規劃問題，而01背包更是典中典問題。

之所以稱為01背包，是因為每個物品只有選與不選兩種狀態。

---

思路

dp就不得不由狀態定義和子問題分解，我們來思索一下。

?定義dp[a][b]為能夠物品選擇范圍為[0, a]且當前背包最多能裝體積為b的物品總量時的最優解。

這樣，我們就可以從小問題推導出大問題的解，應該是這樣的：

考慮選擇范圍為前i個物品，體積為j，有選與不選兩種狀態，取兩種情況最大值。

即dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);

如果 j?< v[i]，則代表放不下這個物品,dp[i][j] = dp[i - 1][j];

---

解題過程

我們可以得到非常直觀的二重循環。

int solve(){for (int i = 1; i <= n; i++)for (int j = 0; j <= m; j++) {if (j < v[i]) dp[i][j] = dp[i - 1][j];else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);}return dp[n][m];
}

優化方案

背包dp有著非常知名的空間優化。

觀察狀態轉移，可以發現：空間可以被優化成1維的。

我們不再用i存儲當前的可選范圍信息，取而代之的是，這個信息隱式地蘊含在每次循環中。?

int solve(){for (int i = 1; i <= n; i++)for (int j = m; j >= v[i]; j--) {dp[j] = max(dp[j], dp[j - v[i]] + w[i]);}return dp[m];
}

這里有一個非常重要的行為：倒序枚舉j。

我們要保證dp來自于上一個i，即不能污染狀態轉移的數據源，考慮到 j 來自j - v[i]，我們倒序枚舉j，就使得j - v[i]不會被j污染。

形象的說

狀態轉移的方向是從前向后->，如果更新順序是從后向前<-，那么每個狀態獲得的新值都不來自這次更新，而是上次。

這樣一來，我們可以保證在計算當前(i)dp[j]時，使用的是上次(i - 1)dp[j]，這樣就等效于二維數組了。

Code

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1005;
int v[N], w[N];
int dp[N];
int n,m;
int solve(){for (int i = 1; i <= n; i++)for (int j = m; j >= v[i]; j--) {dp[j] = max(dp[j], dp[j - v[i]] + w[i]);}return dp[m];
}
int main(){cin >> n >> m;for (int i = 1; i <= n; i++)cin >> v[i] >> w[i];cout << solve();return 0;
}

復雜度

時間復雜度:?O(nm)?//需求解n*m個狀態。

空間復雜度:?O(n) ???//預留dp數組空間

總結

背包問題是非常經典的動態規劃問題，后續將講解完全背包、分組背包等更進一步的問題。