题意

N 种物品，每种无限件，每件体积 v_i。从空背包开始，每次放入一件物品（总体积不能超 V），问有多少种不同的放入顺序能使最后总体积恰好等于 V。不同顺序就算不同方案。答案对 10^9+7 取模。

思路

一句话本质：每种物品可无限用，数排列方案——放入顺序不同就算不同方案。

brute.py 的枚举方式和之前的计数问题有什么不同？

brute.py 中，dfs(cur) 在每一步尝试所有物品 v_i，只要 cur+v_i ≤ V 就递归。这种写法天然区分顺序：先选 v_1 后选 v_2 和先选 v_2 后选 v_1 是不同的递归路径，都会被 cnt += 1 计入。这正是"排列计数"。

而之前的组合计数 brute.py 是逐物品枚举选取数量，顺序被固定为"从物品 1 到物品 N"，不区分排列。

排列和组合在 DP 上的区别是什么？

组合计数：先枚举物品再枚举容量。每种物品只在外层处理一次，顺序被固定，天然不区分排列。

排列计数：先枚举容量再枚举物品。当容量从小到大推进时，dp[c - v] 里可能包含了"以任意物品结尾"的所有排列。对每个 v，从 dp[c - v] 转移到 dp[c]，相当于在已有排列的末尾追加一件物品 v。由于 v 枚举了所有可能物品，末尾追加的物品可以是任意种类——排列顺序就被自然区分了。

为什么先枚举容量再枚举物品就得到排列计数？

考虑容量 4 由体积 1 和 3 凑出的排列：1+3 和 3+1。

先枚举容量法：

• c=1 时，dp[1] 从 dp[0] 转移，可能是物品 1。
• c=4 时，从 dp[3] 转移得到 3+1，从 dp[1] 转移得到 1+3。两者都被计入。

先枚举物品法：

• 处理物品 1 时 c=1→c=4 都可以转移，但物品 3 还没被处理，无法形成 3+1 的排列——排列信息丢失了。

状态定义和转移是什么？

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

初始 dp[0] = 1（空序列是一种排列）。

1
2
3
4for c = 1 to V:
    for each v_i:
        if c >= v_i:
            dp[c] = (dp[c] + dp[c - v_i]) % MOD

转移含义：对于容量 c，枚举最后放入的那件物品 v_i。如果之前已经凑出了 c-v_i 的排列，那么在这些排列末尾追加一件物品 v_i，就得到了容量 c 的一个新排列。

代码

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
27
28
29/**
 * 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> a(N);
    for (int i = 0; i < N; ++i)
        cin >> a[i];
    vector<int> dp(V + 1);
    dp[0] = 1;
    for (int c = 1; c <= V; ++c) {
        for (int v : a) {
            if (c >= v)
                dp[c] = (dp[c] + dp[c - v]) % MOD;
        }
    }
    cout << dp[V] << '\n';
    return 0;
}

复杂度

• 时间：O(N × V)，对每个容量枚举所有物品
• 空间：O(V)，dp 数组大小 V+1

总结

排列计数 vs 组合计数的核心区别在于枚举顺序。先物品后容量 → 组合（物品被固定顺序），先容量后物品 → 排列（最后一步可以选任意物品，顺序被区分）。这是完全背包计数中最容易混淆的一点，记住枚举顺序决定了"顺序是否被计入"。