01 背包计数：f[j] 表示和恰好为 j 的选数方案数，倒序转移统计方案。
OJ: roj
题目 ID: 3141
难度:普及
标签:动态规划01背包问题
创建: 2026-10-01 20:08
更新: 2026-10-07 13:50
后置题目
roj 3169划分大理石B 的可性 DP 层就是 A 教的 0/1 背包状态与倒序避免重复选取：A 用 f[j] += f[j-A_i] 数恰好和为 j 的方案，B 把同一转移改成可达性（或运算）并把数组换成位集，再叠加上多重背包拆分与奇偶剪枝。roj 3549金明的预算方案A 讲透的一维滚动倒序枚举（使 dp[j-cost] 仍是上一轮旧值、每件物品至多选一次）被 B 的分组背包原样复用：B 用同一个倒序容量循环保证同一家族的两个选项不会被叠加、每组至多选一种买法。roj 3144「Coins」 硬币A 教的「一维 01 背包倒序枚举保证每件物品至多取一次」正是 B 暴力层可行性 0/1 背包的原样写法（正解对二进制拆出的每一组仍沿用同一 0/1 语义），B 只在它之上叠加二进制拆分与大整数 bitset 推进。roj 20019食堂打饭B 先用交换论证把队内顺序消掉，再把「进 1 号还是 2 号窗口」做成背包式 DP，其内层 j 从 s 递减枚举正是 A 教的「容量倒序枚举保证每件至多选一次」，用来让 f[j-a_i] 停留在上一层旧值；B 额外叠加的是 b 降序交换论证与 f[j]=min 最晚吃完时刻的新状态。luogu P1064[NOIP 2006 提高组] 金明的预算方案B 的正解 main.cpp 里 `for (int j = n; j >= 0; j--)` 套 `dp[j]=max(dp[j],dp[j-cost]+val)` 直接复用了 A 教的「一维滚动、容量维倒序枚举以保证每个对象至多被选一次」这一步（A 用 f[j]+=f[j-A_i] 计数、B 用 max 取价值，倒序理由完全一致），B 只是在此之上叠加了附件依赖的 2^k 组合枚举与组内互斥。luogu P4141消失之物B 的第一步正是 A 教的「f[j] 表示凑出和 j 的方案数、倒序枚举做 0/1 背包计数」这一模板（B 代码 main.cpp 的 f[j]=(f[j]+f[j-w[i]])%10 与 A 逐字同构），在前置模板之上再叠加 g[j]=f[j]-g[j-w_i] 的补集递推作为新增难点。luogu U661993疯狂的背包问题(11) - 混合背包问题B 的 01 物品分支直接搬用 A 教的「倒序枚举容量→dp[j-v] 是上一轮旧值→每件只取一次」，只在其上按 s_i 追加正序的完全背包分支，属于同一 dp 上的台阶式叠加。luogu U661995疯狂的背包问题(13) - 分组背包B 的分组背包把 A 教的「倒序枚举让物品至多选一次、取旧值」当作组内物品层转移规则，再叠加 previous 冻结上一组状态来实现组内互斥luogu U662039疯狂的背包问题(17) - 求所有最优方案A 教的「把第 i 件物品的决策拆成不选 f[i-1][j] 与选 f[i-1][j-A_i] 两支」正是 B 的 DFS 回溯判定所用的同一对前驱（f[i-1][c] 对应不选、f[i-1][c-v[i]]+w[i] 对应选），B 只是把 A 的计数相加换成相等性检查来枚举所有最优路径，并叠加找最优值、容量遍历与字典序排序。luogu U662097疯狂的背包问题(18) - 求最优方案总数B 的 cnt 计数转移直接套用 A 教的「倒序枚举容量保证每个数至多被选一次」这一步（main.cpp:32 与 A main.py:29 同形），再叠加『更大覆盖、相等累加』与初值全 1 的新流程。luogu U662107疯狂的背包问题(19) - 求恰好装满的最优方案数B 的 cnt 数组就是 A 教的「恰好为 j 的方案数」表：同样 cnt[0]=1、倒序扫描、cnt[c]+=cnt[c-v] 逐项累加方案数，B 只是在外面加了一层 -INF 可达性判断与 dp 最优值合并来选恰好装满的最优方案，属台阶式叠加。
题目描述
给定
输入格式：第一行两个整数
样例：三种方案是 1+1+2 的两种下标组合与 2+2。输入样例：
text
4 4
1 1 2 2输出样例：3
思路
01 背包计数：设
参考代码
Python 版：
python
#!/usr/bin/env python3
# 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-10-01 20:08
# update_at: 2026-10-01 20:08
import sys
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, m = next(data), next(data)
a = [next(data) for _ in range(n)]
# f[j]：已处理的数中选出若干个、和恰好为 j 的方案数（空集对应 f[0] = 1）
f = [0] * (m + 1)
f[0] = 1
for x in a:
# 01 背包倒序枚举，保证每个数只被选一次；f[j] += f[j-x] 即“不选 x / 选 x”两种决策合并
for j in range(m, x - 1, -1):
f[j] += f[j - x]
print(f[m])
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* 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-10-06 11:58
* update_at: 2026-10-06 11:58
*/
#include <cstdio>
typedef long long ll;
const int MAXM = 10005;
int n, m;
int a[105];
ll f[MAXM]; // f[j] 表示已处理的数中选出若干个、和恰好为 j 的方案数
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
// 边界：空集凑出和 0，方案数为 1
f[0] = 1;
// 01 背包计数：每个数只有选/不选两种决策，方案数转移是加法
// j 必须倒序枚举，保证 f[j-x] 还是上一轮的旧值，每个数至多选一次
for (int i = 1; i <= n; i++)
for (int j = m; j >= a[i]; j--)
f[j] += f[j - a[i]];
printf("%lld\n", f[m]);
return 0;
}