背包 DP

如无特殊说明，默认 v 为价值（value），w 为重量（weight）。

01 背包

Luogu-P2871

void solve() {
  int n, m;
  cin >> n >> m;
  vector<int> v(n + 1), w(n + 1);
  vector<int> dp(m + 1);
  for (int i = 1; i <= n; ++i) {
    cin >> w[i] >> v[i];
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = m; j >= w[i]; --j) {
      dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
  }
  cout << *max_element(dp.begin() + 1, dp.end()) << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int t = 1;
  // cin >> t;
  while (t--) {
    solve();
  }
}

完全背包

Luogu-P1616

void solve() {
  int n, m;
  cin >> m >> n;
  vector<int> v(n + 1), w(n + 1);
  vector<int> dp(m + 1);
  for (int i = 1; i <= n; ++i) {
    cin >> w[i] >> v[i];
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = w[i]; j <= m; ++j) {
      dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
  }
  cout << *max_element(dp.begin() + 1, dp.end()) << endl;
}

多重背包

AcWing-5

void solve() {
  int n, m;
  cin >> n >> m;
  vector<int> v(n + 1), w(n + 1), s(n + 1);
  for (int i = 1; i <= n; ++i) {
    cin >> w[i] >> v[i] >> s[i];
  }
  vector<int> dp(m + 1);
  auto process_01 = [&](int v, int w) {
    for (int i = m; i >= w; --i) {
      dp[i] = max(dp[i], dp[i - w] + v);
    }
  };
  for (int i = 1; i <= n; ++i) {
    int base = 1;
    int cs = s[i], cw = w[i], cv = v[i];
    while (cs > base) {
      cs -= base;
      process_01(cv * base, cw * base);
      base *= 2;
    }
    process_01(cv * cs, cw * cs);
  }
  cout << dp[m] << endl;
}

混合背包

Luogu-P1833 按类型分别套用上面三种背包的代码即可。

void solve() {
  string s, e;
  int n;
  cin >> s >> e >> n;

  auto process_time = [&](string s) {
    int h = 0, m = 0;
    int pos = 0;
    while (pos < s.size() && s[pos] != ':') {
      h *= 10;
      h += s[pos] - '0';
      ++pos;
    }
    ++pos;
    while (pos < s.size()) {
      m *= 10;
      m += s[pos] - '0';
      ++pos;
    }
    return h * 60 + m;
  };

  int m = process_time(e) - process_time(s);

  vector<int> w(n + 1), v(n + 1), a(n + 1);
  for (int i = 1; i <= n; ++i) {
    cin >> w[i] >> v[i] >> a[i];
  }
  vector<int> dp(m + 1);
  for (int i = 1; i <= n; ++i) {
    if (!a[i]) {
      for (int j = w[i]; j <= m; ++j) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
      }
    } else {
      int base = 1;
      int k = a[i];
      while (k > base) {
        int cw = w[i] * base;
        int cv = v[i] * base;
        for (int j = m; j >= cw; --j) {
          dp[j] = max(dp[j], dp[j - cw] + cv);
        }
        k -= base;
        base <<= 1;
      }
      int cw = w[i] * k;
      int cv = v[i] * k;
      for (int j = m; j >= cw; --j) {
        dp[j] = max(dp[j], dp[j - cw] + cv);
      }
    }
  }
  cout << *max_element(dp.begin() + 1, dp.end()) << endl;
}

二维费用背包

Luogu-P1855

void solve() {
  int n, m, t;
  cin >> n >> m >> t;
  vector<int> w1(n + 1), w2(n + 1);
  for (int i = 1; i <= n; ++i) {
    cin >> w1[i] >> w2[i];
  }
  vector<vector<int>> dp(m + 1, vector<int>(t + 1));
  for (int i = 1; i <= n; ++i) {
    for (int j = m; j >= w1[i]; --j) {
      for (int k = t; k >= w2[i]; --k) {
        dp[j][k] = max(dp[j][k], dp[j - w1[i]][k - w2[i]] + 1);
      }
    }
  }
  cout << dp[m][t] << endl;
}

分组背包

Luogu-P1757

有 $n$ 件物品和一个大小为 $m$ 的背包，第 $i$ 个物品的价值为 $w_i$， 体积为 $v_i$。同时，每个物品属于一个组，同组内最多只能选择一个物品。 求背包能装载物品的最大总价值。

void solve() {
  int m, n;
  cin >> m >> n;
  unordered_map<int, vector<pair<int, int>>> a;
  for (int i = 1; i <= n; ++i) {
    int w, v, k;
    cin >> w >> v >> k;
    a[k].emplace_back(w, v);
  }
  vector<int> dp(m + 1);
  for (auto &[_, vs] : a) {
    for (int i = m; i >= 0; --i) {
      for (auto &[w, v] : vs) {
        if (i >= w) {
          dp[i] = max(dp[i], dp[i - w] + v);
        }
      }
    }
  }
  cout << *max_element(dp.begin() + 1, dp.end());
}

可以转化成分组背包：有依赖的背包，把物品依赖的选择方案分到同一组。

背包问题变种

输出方案

用 $g_{i,v}$ 表示第 $i$ 件物品占用空间为 $v$ 的时候是否被选择，转移时记录选或不选，输出：

int cur_w = m;
vector<int> selected;

for (int i = n; i >= 1; --i) {
  if (g[i][cur_w]) {
    selected.emplace_back(i);
    cur_w -= w[i];
  }
}

求方案数量

把转移中求最大值变为求和。

01 背包：$d{p}_i=\sum d{p}_i,d{p}_{i-w_i},d{p}_0=1$

求最优方案数量

TODO 重写并测试

for (int i = 0; i < N; i++) {
  for (int j = V; j >= v[i]; j--) {
    int tmp = std::max(dp[j], dp[j - v[i]] + w[i]);
    int c = 0;
    if (tmp == dp[j]) {
      c += cnt[j]; // 如果从dp[j]转移
    }
    if (tmp == dp[j - v[i]] + w[i]) {
      c += cnt[j - v[i]]; // 如果从dp[j-v[i]]转移
    }
    dp[j] = tmp;
    cnt[j] = c;
  }
}
int max = 0; // 寻找最优解
for (int i = 0; i <= V; i++) {
  max = std::max(max, dp[i]);
}
int res = 0;
for (int i = 0; i <= V; i++) {
  if (dp[i] == max) {
    res += cnt[i]; // 求和最优解方案数
  }
}

求第 k 优解

TODO 重写并测试

memset(dp, 0, sizeof(dp));
int i, j, p, x, y, z;
scanf("%d%d%d", &n, &m, &K);
for (i = 0; i < n; i++) {
  scanf("%d", &w[i]);
}
for (i = 0; i < n; i++) {
  scanf("%d", &c[i]);
}
for (i = 0; i < n; i++) {
  for (j = m; j >= c[i]; j--) {
    for (p = 1; p <= K; p++) {
      a[p] = dp[j - c[i]][p] + w[i];
      b[p] = dp[j][p];
    }
    a[p] = b[p] = -1;
    x = y = z = 1;
    while (z <= K && (a[x] != -1 || b[y] != -1)) {
      if (a[x] > b[y]) {
        dp[j][z] = a[x++];
      } else {
        dp[j][z] = b[y++];
      }
      if (dp[j][z] != dp[j][z - 1]) {
        z++;
      }
    }
  }
}
printf("%d\n", dp[m][K]);