题意

N 件物品，每件一个体积 v_i，每件只能选一次。问是否存在一种选法，使所选物品的总体积恰好等于背包容量 V。

思路

一句话本质：判断是否存在一种选法让总体积恰好等于 V，不关心价值，只关心"能不能凑出来"。

brute.py 的做法和瓶颈是什么？

brute.py 枚举 2^N 种选法，对每种选法计算总体积，遇到等于 V 的就输出 true 并退出。N 最大 1000，2^1000 不可能跑完——如果没有符合的方案就需要全部枚举完才能判定 false。

这道题和最大价值版的 01 背包有什么不同？

最大价值版关心的是"在容量不超过 V 的前提下，最大价值是多少"。这里不涉及价值，只问一个布尔问题：容量 V 能不能被恰好凑出来。

容量 c 是否"可达"，取决于什么？

如果存在某个物品体积为 v，且容量 c-v 是可达的，那么选上这个物品后容量 c 也是可达的。换句话说，c 的可达性可以从更小容量的可达性推导出来。

状态定义和转移是什么？

定义 dp[c] 为布尔值，表示容量 c 能否由某些物品恰好凑出。

初始 dp[0] = true（不选任何物品，总体积为 0，当然可达）。

对于每件物品体积 v，容量 c 从 V 到 v 倒序：

1dp[c] = dp[c] || dp[c - v]

含义：要么原本就能凑出 c，要么能凑出 c-v 再加上当前物品就能凑出 c。

为什么容量倒序？

和最大价值版一样，每件物品只能选一次。倒序保证 dp[c - v] 还没有被当前物品影响，避免同一件物品被用多次。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25/**
 * 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<bool> dp(V + 1);
    dp[0] = true;
    for (int i = 0; i < N; ++i) {
        int v;
        cin >> v;
        for (int c = V; c >= v; --c)
            dp[c] = dp[c] || dp[c - v];
    }
    cout << (dp[V] ? "true" : "false") << '\n';
    return 0;
}

复杂度

• 时间：O(N × V)，每件物品遍历 V 个容量
• 空间：O(V)，dp 数组大小 V+1

总结

可行性问题把 dp 值从"最优价值"简化为"布尔可达性"。核心逻辑不变——每件物品只能选一次，容量倒序枚举。dp[0] = true 是基石，其他容量通过 dp[c] |= dp[c - v] 层层推导。