跳到主要内容

AcWing 2. 01 背包问题

本节目标

从二维“不选或选”转移推导一维倒序 DP，求每件物品最多使用一次时的最大价值。

返回背包模型框架

查看 AcWing 原题

题意与约束​

有 n 件物品和容量为 m 的背包。每件 (v, w) 中，v 表示体积，w 表示价值；每件只能选零次或一次，求总体积不超过 m 的最大价值。

第一反应与重复子问题​

枚举选或不选有 2^n 种组合。若已处理物品数量与可用容量相同，后续选择完全相同，适合按“前几件物品、容量”合并状态。

状态定义与转移推导​

令 dp[i][j] 为前 i 件物品在容量 j 内的最大价值。第 i 件不选来自 dp[i-1][j]，选时来自 dp[i-1][j-v]+w。压缩后为 dp[j]=max(dp[j], dp[j-v]+w)，容量必须倒序，确保 dp[j-v] 仍是上一件物品层。

正确性依据​

每个最优方案对当前物品非选即选，两类覆盖且互斥。倒序更新时当前物品只会出现在转移右侧一次，保持二维转移中“最多一次”的语义。

样例执行过程​

样例 (1,2),(2,4),(3,4),(4,5)、m=5。处理前两件后 dp[3]=6，来自旧 dp[1]+4；若正序读取新 dp[2]，会错误地把第二件重复使用。继续倒序处理得到 dp[5]=8。

代码实现​

C++17
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int n, m;
vector<pair<int, int>> items;

int maxValue() {
    vector<int> dp(m + 1, 0);
    for (auto [v, w] : items) {
        // 倒序更新，保证每件物品最多使用一次
        for (int j = m; j >= v; j--) {
            dp[j] = max(dp[j], dp[j - v] + w);
        }
    }
    return dp[m];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    items.resize(n);
    for (auto& [v, w] : items) {
        cin >> v >> w;
    }

    cout << maxValue() << '\n';
    return 0;
}

核心函数只消费准备好的 (v, w) 物品：C++ 的 maxValue() 使用全局的 m 和 items，Python 的 max_value(m, items) 接受准备好的参数，并返回 dp[m]。两种实现的 main 都负责读取输入、调用核心函数、输出答案。

复杂度分析​

时间 O(nm)，空间 O(m)。

边界与易错点​

  • 只在 j >= v 时更新；体积大于容量的物品自然跳过。
  • dp[j] 表示不超过 j，全零初始化允许留下空余容量。
  • 正序会把同一件物品重复加入，和完全背包混淆。

模式迁移​

只要选项最多一次且选择分支来自上一物品层，就使用倒序。若允许无限次，重新证明状态来自本层后改为正序。