题意

N 件物品，每件一个体积 v_i，每件只能选一次。问有多少种不同的选法使总体积恰好等于 V。答案对 10^9+7 取模。

思路

一句话本质：数一数有多少种不同的物品集合，使它们的总体积恰好等于 V。

brute.py 的瓶颈在哪？

brute.py 枚举 2^N 种选法，对总体积等于 V 的进行计数。N=1000 时 2^1000 不可能跑完——不是"慢"，是根本不可行。

从可行性问题的 dp[c]=true/false，如何推到计数？

可行性问题是"容量 c 能不能凑出来"。现在进一步问"能凑出来有几种方案"。布尔值不够用了，需要用整数来累加方案数。

凑出容量 c 的方案数怎么算？

假设我们已经知道容量 c-v 有 k 种方案。每一种方案加上体积为 v 的物品，就得到一种容量为 c 的新方案（物品集合不同，所以是不同的方案）。因此 dp[c] 应该加上 dp[c-v]。

状态定义和转移是什么？

定义 dp[c] = 恰好凑出容量 c 的方案数（对 MOD 取模）。

初始 dp[0] = 1（不选任何物品是凑出容量 0 的唯一方案）。

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

1dp[c] = (dp[c] + dp[c - v]) % MOD

为什么 dp[0] = 1？

因为"一件都不选"本身就是一种方案，它凑出了容量 0。如果没有这个基础值，所有 c=v 的容量都加不上——dp[v] = dp[v] + dp[0] 需要 dp[0] = 1。

为什么容量倒序？

每件物品只能在方案中出现一次（01 背包）。如果正序，物品可能被重复计入方案——一旦 dp[v] 被当前物品更新了，dp[2v] 又会从 dp[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
26/**
 * 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;
const int MOD = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int N, V;
    cin >> N >> V;
    vector<int> dp(V + 1);
    dp[0] = 1;
    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]) % MOD;
    }
    cout << dp[V] << '\n';
    return 0;
}

复杂度

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

总结

计数问题把 dp 值从布尔值升级为整数（方案数）。dp[0] = 1 是关键初始化，它保证了每次"选一件新物品"都有基础方案可以派生。转移逻辑 dp[c] += dp[c-v] 本质是分类加法原理：不同物品集合的方案互不相交，直接相加。