背包問題-01背包

首先我們要明白什麼是01背包，在下述例題中，由於每個物體只有兩種可能的狀態（取與不取），對應二進位中的 \(0\) 和 \(1\)，這類問題便被稱為\(\text{「0-1 背包問題」}\)。

題目描述

有 \(N\) 件物品和一個容量為 \(M\) 的背包。第 \(i\) 件物品的重量是 \(W_i\)，價值是 \(D_i\)。求解將哪些物品裝入背包可使這些物品的重量總和不超過背包容量，且價值總和最大。

輸入格式

第一行：物品個數 \(N\) 和背包大小 \(M\)。

第二行至第 \(N+1\) 行：第 \(i\) 個物品的重量 \(W_i\) 和價值 \(D_i\)。

輸出格式

輸出一行最大價值。

我們可以設狀態\(dp_{i,j}\)為在能放前\(n\)個的前提下，容量為\(j\)的背包所能達到的最大值。
我們在對於第\(i\)個物品時，有以下兩個選則：

• \(dp_{i_j}=dp_{i_j-1}\) (不取)
• \(dp_{i_j}=dp_{i_j}-w_i+d_i\) (取)

綜合一下便是\(dp_{i_j}=\)\(\max\)\((dp_{i_j-1},dp_{i_j}-w_i+d_i)\)

這裡如果直接採用二維數組對狀態進行記錄，會出現 MLE。可以考慮改用滾動數組的形式來優化。

因為對\(dp_i\)影響的只有\(dp_{i-1}\),可以去掉第一維，直接用 \(dp_{i}\) 來表示處理到當前物品時背包容量為 \(i\) 的最大價值，得出以下方程：

• \(dp_{i,j}=\max(dp_{i-1,j},dp_{i-1,j-w_{i}}+v_i)\)

綜上所述

#include <iostream>
using namespace std;
const int maxn = 13010;
int n, W, w[maxn], v[maxn], f[maxn];

int main() {
  cin >> n >> W;
  for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];  // 讀入數據
  for (int i = 1; i <= n; i++)
    for (int l = W; l >= w[i]; l--)
      if (f[l - w[i]] + v[i] > f[l]) f[l] = f[l - w[i]] + v[i];  // 狀態方程
  cout << f[W];
  return 0;
}