背包问题⚓︎

背包问题（ $\text{Knapsack Problem}$ ）是动态规划中的经典问题，通常分为两种主要类型： $\text{0-1}$ 背包问题和完全背包问题。

0-1 背包⚓︎

在 $\text{0-1}$ 背包问题中，每个物品只能选择放入背包或不放入背包。

给定 $n$ 个物品，每个物品有一个重量 $w_i$ 和一个价值 $v_i$ ，以及一个最大承重 $W$ 的背包，目标是选择一些物品放入背包，使得总重量不超过 $W$ ，且总价值最大。

状态定义：设 $dp[i][j]$ 表示前 $i$ 个物品中，容量不超过 $j$ 的背包所能获得的最大价值

状态转移方程：

$dp[i][j] = \begin{cases} dp[i-1][j], & \text{if } j < w_i \\ \max(dp[i-1][j], dp[i-1][j - w_i] + v_i), & \text{if } j \geq w_i \end{cases}$

边界条件：

$\begin{aligned} dp[0][j] &= 0 \quad (0 \leq j \leq W) \\ dp[i][0] &= 0 \quad (0 \leq i \leq n) \end{aligned}$

采药

有一个背包，最大承重为 $t$ ，有 $m$ 种物品，每种物品有一个重量 $w_i$ 和一个价值 $v_i$ 。现在要从中选择一些物品放入背包，每种物品最多只能选择一次。要求总重量不超过 $t$ ，并且总价值最大。

标准DP空间优化

C++

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int t, m;
  cin >> t >> m;
  vector<int> weights(m + 1), values(m + 1);
  for (int i = 1; i <= m; ++i) { cin >> weights[i] >> values[i]; }
  vector<vector<int>> dp(m + 1, vector<int>(t + 1, 0));
  for (int i = 1; i <= m; ++i) {
    for (int j = 1; j <= t; ++j) {
      if (j >= weights[i]) {  // 可以选择放入第 i 个物品或者不放入
        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]);
      } else {  // 容量不足，只能选择不放入
        dp[i][j] = dp[i - 1][j];
      }
    }
  }
  cout << dp[m][t] << '\n';
  return 0;
}

由于 $dp[i][j]$ 只依赖于 $dp[i-1][j]$ 和 $dp[i-1][j - w_i]$ ，可以将二维数组优化为一维数组。

C++

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int t, m;
  cin >> t >> m;
  vector<int> weights(m + 1), values(m + 1);
  for (int i = 1; i <= m; ++i) { cin >> weights[i] >> values[i]; }
  vector<int> dp(t + 1, 0);
  for (int i = 1; i <= m; ++i) {
    for (int j = t; j >= weights[i]; --j) {  // 逆序遍历, 保证 dp[j-weights[i]] 是上一行的结果
      dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
    }
  }
  cout << dp[t] << '\n';
  return 0;
}

带依赖的 0-1 背包⚓︎

在某些情况下，物品之间可能存在依赖关系，即某些物品只能在其他物品被选中时才能被选中。这种情况下的 $\text{0-1}$ 背包问题称为带依赖的 $\text{0-1}$ 背包问题。

树形依赖

如果依赖是树形结构, 可以用树形 $\text{dp}$ 解决。

金明的预算方案

有一个容量为 $n$ 的背包， $m$ 个可选的物品，每个物品有一个价格 $v_i$ 和一个重要度 $p_i$ ，物品总价值为 $v_i \times p_i$ 。但是有些物品是附属物品，只能在主件物品购买的情况下购买。每个主件物品可以有 $0$ 个、 $1$ 个或 $2$ 个附属物品。附属物品不再有附属物品。在不超过预算的情况下, 使得购买的物品总价值最大.

C++

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> weights(m + 1), values(m + 1), parents(m + 1);
  vector<int> kings(m + 1);               // kings[i]表示物品i是否为主件物品
  vector<vector<int>> dependents(m + 1);  // dependents[i]表示物品i的附属物品
  for (int i = 1; i <= m; ++i) {
    cin >> weights[i] >> values[i] >> parents[i];
    values[i] *= weights[i];  // 转化为价值背包
    if (parents[i] == 0) {    // 物品i为主件物品
      kings[i] = 1;
    } else {  // 物品i为物品parents[i]的附属物品
      dependents[parents[i]].push_back(i);
    }
  }

  vector<int> dp(n + 1, 0);
  for (int i = 1; i <= m; ++i) {
    // 只处理主件物品
    if (kings[i] == 0) { continue; }
    // 枚举主件物品i的所有可能的组合(包括不选任何附属物品)
    for (int j = n; j >= weights[i]; --j) {
      // 先不选附属物品, 只考虑主件物品
      dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
      // 枚举附属物品的所有组合, 此处假设附属不超过32件
      int m = dependents[i].size();
      for (int s = 1; s < (1 << m); ++s) {
        int total_weight = weights[i];  // 主件物品i的重量, 必须选
        int total_value  = values[i];   // 主件物品i的价值, 必须选
        for (int k = 0; k < m; ++k) {
          if ((s & (1 << k)) != 0) {  // 选择附属物品k
            total_weight += weights[dependents[i][k]];
            total_value  += values[dependents[i][k]];
          }
        }
        if (total_weight <= j) { dp[j] = max(dp[j], dp[j - total_weight] + total_value); }
      }
    }
  }
  cout << dp[n] << '\n';

  return 0;
}

分组背包⚓︎

在分组背包问题中，物品被分成若干组，每组中只能选择一个物品放入背包。

给定 $n$ 个物品，这些物品被分成 $g$ 组，每个物品有一个重量 $w_i$ 和一个价值 $v_i$ ，以及一个最大承重 $W$ 的背包，目标是选择一些物品放入背包，使得总重量不超过 $W$ ，且总价值最大。

分组背包的状态定义与 $\text{0-1}$ 背包类似，设 $dp[i][j]$ 表示前 $i$ 组物品中，容量不超过 $j$ 的背包所能获得的最大价值。每组内分别选择一个物品进行状态转移。

通天之分组背包

有一个容量为 $m$ 的背包， $n$ 个可选的物品，每个物品有一个重量 $w_i$ 、一个价值 $v_i$ 和一个组别 $g_i$ 。现在要从中选择一些物品放入背包，要求总重量不超过 $m$ ，并且总价值最大。但对于每个组别，只能选择其中的一个物品放入背包。

C++

#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
using namespace std;

int main() {
  int m, n;
  cin >> m >> n;
  vector<int> weights(n + 1), values(n + 1);
  map<int, vector<int>> groups;
  for (int i = 1; i <= n; ++i) {
    int w, v, g;
    cin >> w >> v >> g;
    groups[g].push_back(i);
    weights[i] = w;
    values[i]  = v;
  }
  vector<int> dp(m + 1, 0);
  for (const auto &[_, items] : groups) {
    for (int j = m; j >= 0; --j) {
      for (auto i : items) {
        if (j >= weights[i]) { dp[j] = max(dp[j], dp[j - weights[i]] + values[i]); }
      }
    }
  }
  cout << dp[m] << '\n';
}

完全背包⚓︎

在完全背包问题中，每个物品可以选择放入背包多次。

给定 $n$ 个物品，每个物品有一个重量 $w_i$ 和一个价值 $v_i$ ，以及一个最大承重 $W$ 的背包，目标是选择一些物品放入背包，使得总重量不超过 $W$ ，且总价值最大。

状态定义：设 $dp[i][j]$ 表示前 $i$ 个物品中，容量不超过 $j$ 的背包所能获得的最大价值

状态转移方程：

$dp[i][j] = \begin{cases} dp[i-1][j], & \text{if } j < w_i \\ \max(dp[i-1][j], dp[i][j - w_i] + v_i), & \text{if } j \geq w_i \end{cases}$

边界条件：

$\begin{aligned} dp[0][j] &= 0 \quad (0 \leq j \leq W) \\ dp[i][0] &= 0 \quad (0 \leq i \leq n) \end{aligned}$

疯狂的采药

有一个背包，最大承重为 $t$ ，有 $m$ 种物品，每种物品有一个重量 $w_i$ 和一个价值 $v_i$ 。现在要从中选择一些物品放入背包，每种物品可以选任意次。要求总重量不超过 $t$ ，并且总价值最大。

标准DP空间优化

MLE

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int t, m;
  cin >> t >> m;
  vector<int> weights(m + 1), values(m + 1);
  for (int i = 1; i <= m; ++i) { cin >> weights[i] >> values[i]; }
  vector<vector<int64_t>> dp(m + 1, vector<int64_t>(t + 1, 0));
  for (int i = 1; i <= m; ++i) {
    for (int j = 1; j <= t; ++j) {
      dp[i][j] = dp[i - 1][j];
      if (j >= weights[i]) { dp[i][j] = max(dp[i][j], dp[i][j - weights[i]] + values[i]); }
    }
  }
  cout << dp[m][t] << '\n';
  return 0;
}

由于 $dp[i][j]$ 只依赖于 $dp[i-1][j]$ 和 $dp[i][j - w_i]$ ，可以将二维数组优化为一维数组。

注意这里需要正序遍历容量 $j$ ，以确保每个物品可以被多次选择。

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int t, m;
  cin >> t >> m;
  vector<int> weights(m + 1), values(m + 1);
  for (int i = 1; i <= m; ++i) { cin >> weights[i] >> values[i]; }
  vector<int64_t> dp(t + 1, 0);
  for (int i = 1; i <= m; ++i) {
    for (int j = weights[i]; j <= t; ++j) { dp[j] = max(dp[j], dp[j - weights[i]] + values[i]); }
  }
  cout << dp[t] << '\n';
  return 0;
}

多重背包⚓︎

在多重背包问题中，每个物品有一个数量限制，表示每种物品最多可以选择多少次。

给定 $n$ 个物品，每个物品有一个重量 $w_i$ 、一个价值 $v_i$ 和一个数量限制 $c_i$ ，以及一个最大承重 $W$ 的背包，目标是选择一些物品放入背包，使得总重量不超过 $W$ ，且总价值最大。

状态定义：设 $dp[i][j]$ 表示前 $i$ 个物品中，容量不超过 $j$ 的背包所能获得的最大价值

状态转移方程：

$dp[i][j] = \max_{0 \le k \le \min(c_i, \lfloor j / w_i \rfloor)} \left( dp[i-1][j - k \cdot w_i] + k \cdot v_i \right)$

边界条件：

$\begin{aligned} dp[0][j] &= 0 \quad (0 \leq j \leq W) \\ dp[i][0] &= 0 \quad (0 \leq i \leq n) \end{aligned}$

宝物筛选

有一个容量为 $w$ 的背包， $n$ 个可选的物品，每个物品有一个重量 $w_i$ 、一个价值 $v_i$ 和一个数量限制 $c_i$ 。现在要从中选择一些物品放入背包，要求总重量不超过 $w$ ，并且总价值最大。但每种物品最多只能选择 $c_i$ 件。

TLE

时间复杂度 $O(n \cdot w \cdot \max(c_i))$ ，当 $c_i$ 较大时效率较低。

标准DP空间优化

C++

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int n, w;
  cin >> n >> w;
  vector<int> weights(n + 1), values(n + 1), counts(n + 1);
  for (int i = 1; i <= n; ++i) { cin >> values[i] >> weights[i] >> counts[i]; }
  vector<vector<int>> dp(n + 1, vector<int>(w + 1, 0));
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j <= w; ++j) {
      dp[i][j] = dp[i - 1][j];                                       // 不放入第i件物品
      for (int k = 1; k <= counts[i] && k * weights[i] <= j; ++k) {  // 放入k件第i件物品
        dp[i][j] = max(dp[i][j], dp[i - 1][j - k * weights[i]] + k * values[i]);
      }
    }
  }
  cout << dp[n][w] << '\n';
  return 0;
}

由于 $dp[i][j]$ 只依赖于 $dp[i-1][j]$ 和 $dp[i-1][j - k \cdot w_i]$ ，可以将二维数组优化为一维数组。

C++

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int n, w;
  cin >> n >> w;
  vector<int> weights(n + 1), values(n + 1), counts(n + 1);
  for (int i = 1; i <= n; ++i) { cin >> values[i] >> weights[i] >> counts[i]; }
  vector<int> dp(w + 1, 0);
  for (int i = 1; i <= n; ++i) {
    // 注意这里要逆序遍历, 保证 dp[j-k*weights[i]] 是上一行的结果
    for (int j = w; j >= weights[i]; --j) {
      for (int k = 1; k <= counts[i] && k * weights[i] <= j; ++k) {
        dp[j] = max(dp[j], dp[j - k * weights[i]] + k * values[i]);
      }
    }
  }
  cout << dp[w] << '\n';
  return 0;
}

二进制优化⚓︎

可以将每种物品的数量限制 $c_i$ 拆成若干组，组内数量依次为 $1, 2, 4, \dots$ ，最后一组为剩余数量。这样任意 $0 \sim c_i$ 的取法都能由这些组的和表示出来，从而将多重背包问题转化为多个 $\text{0-1}$ 背包问题。

分解方法

如果某种物品的数量限制为 $13$ ，可以将其拆成 $1 + 2 + 4 + 6$ 。这样就能表示从 $0$ 到 $13$ 的任意取件数，并将该物品转化为若干件只能选择一次的新物品。

宝物筛选

C++

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int n, w;
  cin >> n >> w;
  vector<int> weights(n + 1), values(n + 1), counts(n + 1);
  for (int i = 1; i <= n; i++) { cin >> values[i] >> weights[i] >> counts[i]; }
  vector<int> dp(w + 1, 0);
  for (int i = 0; i < weights.size(); ++i) {
    int count = counts[i];
    for (int k = 1; count > 0; k <<= 1) {  // 将count拆分为若干个2的幂次方之和
      int use     = min(k, count);         // 不足2的幂次方则全部使用, 则单独作为一组
      count      -= use;
      int weight  = use * weights[i];
      int value   = use * values[i];
      for (int j = w; j >= weight; --j) { dp[j] = max(dp[j], dp[j - weight] + value); }
    }
  }
  cout << dp[w] << '\n';
  return 0;
}

单调队列优化⚓︎

对于每种物品，可以将其对容量的贡献分为若干个模 $w_i$ 的子问题，每个子问题可以使用单调队列进行优化。

对于固定物品 $i$ ，考虑容量 $j$ 与物品数量 $k$ 的关系：

$dp[i][j] = \max_{0 \le k \le c_i,\, k w_i \le j} \big( dp[i-1][j - k w_i] + k v_i \big)$

$j$ 只能从 $j - k w_i$ 转移而来，其他的 $j^{'}$ 不会对它的结果产生影响，因此可以对 $j$ 进行 同余分类：

对 $m = 0,1,\dots,w_i-1$ ，考虑所有 $j$ 满足 $j \equiv m \pmod{w_i}$
设 $j = m + t \cdot w_i$ ，其中 $t \ge 0$ ，表示可以选择 $t$ 件物品 $i$

代入公式：

$dp[i][m + t w_i] = \max_{0 \le k \le \min(c_i, t)} \big( dp[i-1][m + (t-k) w_i] + k v_i \big)$

注意到上式是对一个区间的最大值进行求解，考虑将其转化为滑动窗口最大值问题。

上式中的计算依赖于 $k$ ，而当 $t$ 变化时， $k$ 的取值范围也随之变化，导致窗口中每个候选项的贡献值都会动态改变，无法直接用滑动窗口维护。因此需要将原式转化为一个不显式依赖 $k$ 的形式。

设：

$g(t-k) = dp[i-1][m + (t-k) w_i] - (t-k)v_i$

则：

$dp[i][m + t w_i] = \max_{0 \le k \le \min(c_i, t)} \big( g(t-k) + t v_i \big) = \max_{0 \le k \le \min(c_i, t)} \big( g(t-k) \big) + t v_i$

在归一化后， $k$ 只表示窗口中的相对位置，不再影响候选项的值
注意到 $t v_i$ 对所有 $k$ 相同，因此只需要求 $g(t-k)$ 的滑动最大值

于是，对于每个同余类 $m$ ，问题变成一个 长度为 $c_i+1$ 的滑动窗口最大值 问题。

同余类与滑动窗口示意

设当前物品的重量 $w_i = 3$ 、数量限制 $c_i = 2$ ，固定同余类 $m = 1$ 。

此时只会处理这一组同余的容量：

$j = 1,\ 4,\ 7,\ 10,\ 13,\ \dots$

令 $j = m + t w_i$ ，则对应：

$t = 0,\ 1,\ 2,\ 3,\ 4,\ \dots$

对于每个 $t$ ，我们维护：

$g(t) = dp[i-1][m + t w_i] - t v_i$

例如当 $t = 3$ 时，对应容量 $j = 10$ 。由于最多只能选 $c_i = 2$ 件当前物品，所以合法转移只会来自窗口 $[t-c_i, t] = [1, 3]$ ，也就是比较：

$g(1),\ g(2),\ g(3)$

flowchart LR
  T0["t = 0<br/>j = 1<br/>g(0)"]
  T1["t = 1<br/>j = 4<br/>g(1)"]
  T2["t = 2<br/>j = 7<br/>g(2)"]
  T3["t = 3<br/>j = 10<br/>g(3)"]
  T4["t = 4<br/>j = 13<br/>g(4)"]
  T0 --> T1 --> T2 --> T3 --> T4

  classDef active fill:#dff3e4,stroke:#2f855a,stroke-width:2px;
  classDef current fill:#fde68a,stroke:#b45309,stroke-width:2px;
  class T1,T2 active;
  class T3 current;

图中绿色和黄色节点就是当前窗口中的候选状态。随着 $t$ 从小到大递增，这个窗口也同步右移，因此可以用单调队列维护窗口内的最大值。

实现思路⚓︎

遍历同余类 $m$
维护一个单调队列，存储 $(t, g(t))$ ，队列保证 $g(t)$ 单调递减
对每个 $t$ ：
- 弹出队列中窗口左端过期的元素，保证转移中使用的物品数不超过 $c_i$
- 队首 $front$ 对应的 $g(front)$ 即为当前最大值
- 更新 $dp[i][m + t w_i] = g(front) + t v_i$

这里必须先用当前尚未更新的 dp[j] 计算 $g(t)$ ，再把 $(t, g(t))$ 放入队列，最后用队首更新 dp[j]。这样虽然使用的是一维 dp，但队列中保存的仍然是当前物品加入前的候选值，因此不会把同一件物品重复计算多次。

宝物筛选

单调队列优化

时间复杂度： $O(n W)$ 。

C++

#include <deque>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int n, W;
  cin >> n >> W;
  vector<int> weights(n + 1), values(n + 1), counts(n + 1);
  for (int i = 1; i <= n; i++) { cin >> values[i] >> weights[i] >> counts[i]; }
  vector<int> dp(W + 1, 0);
  for (int i = 1; i <= n; i++) {
    int w = weights[i], v = values[i], c = counts[i];
    for (int m = 0; m < w; m++) {  // 按余数分类
      deque<pair<int, int>> dq;    // {t, g(t)} (1)
      for (int t = 0; m + t * w <= W; t++) {
        int j = m + t * w;
        // 队列头元素过期
        while (!dq.empty() && t - dq.front().first > c) { dq.pop_front(); }
        int g = dp[j] - t * v;
        // 单调队列维护最大值, 根据指标 g(t) = dp[i-1][j] - t*v 进行维护
        while (!dq.empty() && dq.back().second <= g) { dq.pop_back(); }
        dq.emplace_back(t, g);
        dp[j] = dq.front().second + t * v;
      }
    }
  }

  cout << dp[W] << "\n";
  return 0;
}

此处存储 $(t, g(t))$ ，方便判断队首元素是否过期，以及进行备份。因为 $dp$ 数组会被覆盖，当遍历到 $t$ 时，需要根据之前的 $dp$ 值计算 $g(t)$ ，但 $dp$ 数组已经被更新过了。
使用队列存储 $g(t)$ 相对于始终存储了 $i-1$ 行的 $dp$ 数组，可以避免这个问题。
另一种方法是类似 $\text{0-1}$ 背包那样，从后向前遍历 $j$ 。

背包的前 k 大解⚓︎

普通的 $\text{0-1}$ 背包通常只求最优解。若要进一步维护前 $k$ 大解，可以在状态中额外记录一个长度为 $k$ 的有序解序列。

例如， $dp[i][j][t]$ 表示前 $i$ 个物品、容量为 $j$ 时，第 $t$ 大的价值。

在状态转移时，普通背包问题的 $dp(i,j)$ 由“不选当前物品”和“选当前物品”两类转移而来。因此维护前 $k$ 大解时，需要把这两组有序解合并，并保留前 $k$ 大结果。

多人背包

有一个容量为 $v$ 的背包， $n$ 个可选的物品，每个物品有一个重量 $w_i$ 和一个价值 $val_i$ 。现在要从中选择一些物品放入背包，要求总重量不超过 $v$ 。请维护前 $k$ 大方案的总价值。

标准DP空间优化

MLE

C++

#include <algorithm>
#include <cstdint>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int k, v, n;
  cin >> k >> v >> n;
  vector<int> weights(n + 1);
  vector<int> values(n + 1);
  for (int i = 1; i <= n; i++) { cin >> weights[i] >> values[i]; }

  using VI   = vector<int>;
  using VVI  = vector<VI>;
  using VVVI = vector<VVI>;
  VVVI dp    = VVVI(n + 1, VVI(v + 1, VI(k, INT32_MIN)));
  for (int i = 0; i <= n; i++) { dp[i][0][0] = 0; }

  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j <= v; ++j) {
      vector<int> not_chosen = dp[i - 1][j];  // 不选第i个物品
      if (j >= weights[i]) {                  // 选第i个物品, 需要加上物品的价值
        vector<int> chosen = dp[i - 1][j - weights[i]];
        for (int l = 0; l < k; l++) { chosen[l] += values[i]; }
        not_chosen.insert(not_chosen.end(), chosen.begin(), chosen.end());
      }
      // 取前 k 大的解
      sort(not_chosen.begin(), not_chosen.end(), greater<>());
      not_chosen.resize(k);
      dp[i][j] = not_chosen;
    }
  }

  // 计算前 k 个最优解的总价值
  int ans = 0;
  for (int i = 0; i < k; i++) { ans += dp[n][v][i]; }

  cout << ans << '\n';
  return 0;
}

考虑到解序列总是有序的，因此可以使用合并排序的方法，将两个有序的序列合并为一个有序的序列，时间复杂度为 $O(k)$ 。同时，类似 $\text{0-1}$ 背包问题，可以将多维数组降重。

C++

#include <cstdint>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  int k, v, n;
  cin >> k >> v >> n;
  vector<int> weights(n + 1);
  vector<int> values(n + 1);
  for (int i = 1; i <= n; i++) { cin >> weights[i] >> values[i]; }
  vector<vector<int>> dp(v + 1, vector<int>(k, INT32_MIN));
  dp[0][0] = 0;

  for (int i = 1; i <= n; i++) {
    for (int j = v; j >= weights[i]; j--) {
      vector<int> now(k, 0);           // 保存当前状态的解
      int not_choose = 0, choose = 0;  // 指向两个转移状态的第k大的解
      for (int l = 0; l < k; ++l) {
        if (dp[j][not_choose] > dp[j - weights[i]][choose] + values[i]) {  // 合并排序
          now[l] = dp[j][not_choose];
          not_choose++;
        } else {
          now[l] = dp[j - weights[i]][choose] + values[i];
          choose++;
        }
      }
      dp[j] = now;
    }
  }

  // 计算前 k 个最优解的总价值
  int ans = 0;
  for (int i = 0; i < k; i++) { ans += dp[v][i]; }

  cout << ans << '\n';
  return 0;
}

背包问题⚓︎

0-1 背包⚓︎

带依赖的 0-1 背包⚓︎

分组背包⚓︎

完全背包⚓︎

多重背包⚓︎

二进制优化⚓︎

单调队列优化⚓︎

实现思路⚓︎

背包的前 k 大解⚓︎

评论