题意

N 件物品，每件只能选一次。第 i 件体积 v_i，价值 w_i。背包容量 V。挑选一些物品使总体积不超过 V 且总价值最大，输出最大价值。

思路

一句话本质：每件物品只能选或不选，容量有限制，问最大总价值。

为什么不能直接枚举所有选法？

brute.py 用位掩码枚举了 2^N 种选法，每次检查总体积并更新最优价值。N 最大到 1000，2^1000 是天文数字，根本无法跑完。

既然不能全枚举，我们如何逐步处理这些物品？

可以把物品一个一个地拿出来决策。每处理一件物品，我们只面临两个选择：选它或不选它。

选或不选这个物品，影响了什么？

选了它就占了容量、增加了价值；不选就什么也不变。也就是说，当我们处理到第 i 个物品时，唯一需要关心的状态是"目前已经占用了多少容量"。

如果有多种方式占用相同的容量，我们只需要保留哪一种？

只保留总价值最大的那种。因为后续物品只关心剩余容量还有多少，不关心前面具体选了哪些物品。不同路径到达相同容量，价值更大的那条路径永远更优。这正是 DP 的核心——最优子结构。

状态定义和转移是什么？

定义 dp[c] 表示占用容量 c 时能获得的最大价值。

初始 dp[0] = 0，其他为 0（一件都不选时价值为 0）。

对于每件物品 (v, w)，考虑容量 c 从 V 到 v 倒序：

1dp[c] = max(dp[c], dp[c - v] + w)

含义：要么不选（保持 dp[c]），要么选（从 c-v 转移来，加上价值 w）。

为什么容量必须倒序枚举？

因为每件物品只能选一次。如果正序枚举，处理小的 c 时更新了 dp[c]，后面更大的 c’ = c + v 再次用到 dp[c] 时会包含这件物品的影响，等于同一件物品被选了两次。倒序能保证 dp[c - v] 是"没选过当前物品"时的状态。

代码

C++17 正解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-08 23:11
 * update_at: 2026-08-08 23:11
 */
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int N, V;
    cin >> N >> V;
    vector<int> dp(V + 1);
    for (int i = 0; i < N; ++i) {
        int v, w;
        cin >> v >> w;
        for (int c = V; c >= v; --c)
            dp[c] = max(dp[c], dp[c - v] + w);
    }
    cout << dp[V] << '\n';
    return 0;
}

Python 版本（会超内存）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20import sys

def ints():
    for x in sys.stdin.buffer.read().split():
        yield int(x)

it = ints()
n = next(it)
C = next(it)
f = [0] * (C + 1)

for _ in range(n):
    vol = next(it)
    val = next(it)
    if vol > C:
        continue
    for c in range(C, vol - 1, -1):
        f[c] = f[c] if f[c] >= f[c - vol] + val else f[c - vol] + val

print(f[C])

main.py 的状态定义和倒序转移与 C++ 完全一致，样例输出 8，随机对拍 300 组也与 brute.py 一致，本机最大数据（$N = V = 10^3$）耗时约 0.1s。但本题内存限制只有 3 MB（3072 KB），而 CPython 解释器本身的常驻内存就接近 10 MB，实测这份代码的峰值 RSS 约 9948 KB——还没算上 f 数组就已经超出限制。因此它在洛谷上必然 MLE，这里只作为 Python 写法对照，正式提交请使用 main.cpp。

复杂度

• 时间：O(N × V)，每件物品遍历 V 个容量
• 空间：O(V)，dp 数组大小 V+1
• main.py 的时间与空间复杂度相同，但解释器运行时开销约 10 MB，超过本题 3 MB 的内存限制，无法通过。

总结

01 背包的核心是每件物品只能选一次，通过容量倒序枚举来保证。dp[c] 记录容量 c 下的最优价值，转移时取"不选"和"选"的最大值。