https://www.acwing.com/problem/content/description/2/

选还是不选 这是一个问题。也是 0-1 名字的由来。也就是物品的数量只有一个。

如果暴力去做，每个物品选或者不选，复杂度为 $O(2^n)$，需要使用动态规划降低复杂度。

总结一下代码模板

for (int i = 0; i < n; i ++) { // 遍历物品
    for (int j = capacity; j >= weight[i]; j --) { // 遍历背包容量
				dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
		}
}

二维 DP

<aside> <img src="/icons/light-bulb_gray.svg" alt="/icons/light-bulb_gray.svg" width="40px" /> 核心问题

f[i][j] = ?

不放物品 i → dp[i - 1][j]

放物品 i → dp[i - 1][j - weights[i]] + values[i]

Initialization

j = 0 → dp[i][0] = 0;

i= 0 → 放第一个物品

</aside>

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n, capacity;
  cin >> n >> capacity;

  vector<int> weights(n);
  vector<int> values(n);
  for (int i = 0; i < n; i++) {
    cin >> weights[i] >> values[i];
  }

  vector<vector<int>> f(n, vector<int>(capacity + 1));
  
  // Initialization
  for (int j = weights[0]; j <= capacity; j++) {
    f[0][j] = values[0];
  }

  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= capacity; j++) {
      if (j < weights[i]) f[i][j] = f[i - 1][j];
      else f[i][j] = max(f[i - 1][j], f[i - 1][j - weights[i]] + values[i]);
    }
  }

  cout << f[n - 1][capacity] << endl;

  return 0;
}

一维 DP

他山之石: https://www.acwing.com/file_system/file/content/whole/index/content/1061/

01背包问题 https://www.acwing.com/problem/content/2/

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n, capacity;
  cin >> n >> capacity;

  vector<int> weights(n);
  vector<int> values(n);

  for (int i = 0; i < n; i++) {
    cin >> weights[i] >> values[i];
  }

  vector<int> f(capacity + 1);
  for (int i = 0; i < n; i++) {
    for (int j = capacity; j >= weights[i]; j--) {
      f[j] = max(f[j], f[j - weights[i]] + values[i]);
    }
  }
  cout << f[capacity] << endl;

  return 0;
}