把有限枚砝码逐个展开成 0/1 物品，按总重量做布尔可达性背包，最后统计所有可达的正整数重量。
OJ: luogu
题目 ID: P2347
难度:普及-
标签:动态规划背包01背包
创建: 2026-06-19 14:57
更新: 2026-10-07 10:45
前置题目
luogu P1164小 A 点菜B（main-rainboy.cpp 分支）把 A 教的「每件最多选一次、容量倒序枚举」这一 0/1 背包转移直接复用：先把每枚砝码逐枚展开成 0/1 物品，再对 j 从 sum 到 w 倒序做 dp[j]|=dp[j-w]，只把 A 的方案数累加换成布尔可达性并最后统计可达重量数。luogu P2871[USACO07DEC] Charm Bracelet SB 的 main-rainboy.cpp 分支把 A 教的「每件物品只能选一次，所以容量必须倒序枚举」原样套到逐枚展开的砝码上（for j = sum..w[i]），只把 max 值转移改成布尔可达 dp[j] |= dp[j-w[i]]，并在此基础上新增逐枚展开与可达重量计数。luogu U663295疯狂的背包问题(2) - 01背包问题（可行性问题）B 的 main-rainboy.cpp 把 A 教的「布尔可达性 dp + 容量倒序枚举（每件最多选一次）」原样用作其可达性背包主体：A 是 dp[c]=dp[c]||dp[c-v] 单问 V 是否可达，B 先叠加 A 未教的「每种多枚砝码逐枚展开成 0/1 物品」这一层，再用同一倒序转移 dp[j]|=dp[j-w] 把可达性从单点扩到所有重量并计数（bitset 版 dp|=dp<<w 是同一转移的位并行写法），属台阶式叠加而非同难度孪生。
后置题目
roj 3169划分大理石B 的 main.py 逐块执行 A 教的位集可行性转移 dp|=dp<<w（reach|=reach<<w），只是把 A 的“统计可达重量个数”换成“查询第 total/2 位是否可达”并叠加全奇/总价值奇偶剪枝。roj 3659货币系统B 判定面额 v 是否冗余的那一步复用了 A 教的「可达集合编码成位集 + 左移取并」：A 用 dp|=(dp<<value) 加入一枚砝码，B 用同一平移取并把可达位集按 coin 闭包后查 (reachable>>v)&1，只把单枚 0/1 物品换成无限张、并在其上叠加升序删冗余贪心。roj 2045usaco-3.1.6 邮票B 的正解直接复用 A 教的「可达性编码成位集合 + 左移或转移」这一状态设计与关键实现，只在外面叠加 K 轮分层、K*maxA 上界与连续可达前缀计数。luogu U662107疯狂的背包问题(19) - 求恰好装满的最优方案数B 的恰好装满解法直接沿用 A 的「用可达性初值区分可达与不可达」这一步，把 A 的 dp[0]=true 换成 dp[0]=0 可达、其余 -INF 不可达，并再加一层前驱可达性判断来做方案计数（main.cpp:35）。luogu P1776宝物筛选B 的二进制拆分正是 A 教的「把有件数限制的物品展开成 0/1 物品后做一维 01 背包」这一步的升级：A 逐枚展开、价值退化成布尔可达，B 用 1,2,4…打包把展开数量从 O(m_i) 压到 O(log m_i)，转移仍是有件数限制物品转 0/1 物品的同一模式，B 另外叠加的只是拆分组数与组内重量价值计算。luogu P6771[USACO05MAR] Space Elevator 太空电梯B 直接沿用了 A 教的“布尔 dp 表示某个重量/高度是否可达”的可达性背包状态设计（main.cpp 中 dp[j] 转移），再叠加按 a_i 排序与 used 数组限制每种方块数量这两步新流程，因此是 A 基础上的台阶题。luogu P8742[蓝桥杯 2021 省 AB] 砝码称重B 的 main.cpp 直接沿用 A 教的「由已有可达状态加砝码重量推出新可达状态」这一可行性转移，只把可达量从总重量换成带偏移量的两侧差值，并新增负下标偏移与正差值统计luogu U663791疯狂的背包问题(9) - 多重背包问题 IIB 的解法骨架正是 A 教的那一步「有件数限制的物品展开成 0/1 物品后跑 01 背包」：A 逐枚展开砝码并把它当 0/1 物品转移，B 用 1,2,4…二进制打包把展开数量从 O(s_i) 压到 O(log s_i)，每个包仍当作独立 01 物品跑同一套一维 01 背包（main.cpp 的 for (c=V;c>=pack_v;--c) dp[c]=max(dp[c],dp[c-pack_v]+pack_w)），B 甚至把 A 的逐枚展开写作「原来的做法」作对照，额外叠加的只是二进制分组流程与价值最大化；难度 普及/提高- → 普及+/提高 台阶方向正确。
题意
现在有 6 种砝码：
1g, 2g, 3g, 5g, 10g, 20g
每种砝码都有若干枚，问利用这些砝码一共能称出多少种不同的正整数重量。
思路
一句话本质：每种砝码有 cnt[i] 枚——把每枚砝码看成一个独立的 0/1 物品，用 bitset 做多重可行性背包，统计可达正整数重量数。
先看最直接的暴力：
cpp
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;
const int TYPE_CNT = 6;
const int weight_value[TYPE_CNT + 1] = {0, 1, 2, 3, 5, 10, 20};
const int MAXW = 1005;
int cnt[TYPE_CNT + 1]; // 每种砝码的数量
bool reachable[MAXW]; // reachable[w] = 是否能称出重量 w
int total_weight; // 所有砝码总重量
void dfs(int type_id, int current_sum) {
if (type_id > TYPE_CNT) {
if (current_sum > 0) {
reachable[current_sum] = true;
}
return;
}
for (int use_cnt = 0; use_cnt <= cnt[type_id]; use_cnt++) {
dfs(type_id + 1, current_sum + use_cnt * weight_value[type_id]);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
total_weight = 0;
for (int i = 1; i <= TYPE_CNT; i++) {
cin >> cnt[i];
total_weight += cnt[i] * weight_value[i];
}
memset(reachable, 0, sizeof(reachable));
dfs(1, 0);
int answer = 0;
for (int w = 1; w <= total_weight; w++) {
if (reachable[w]) {
answer++;
}
}
cout << "Total=" << answer << '\n';
return 0;
}brute.cpp 对 6 种砝码分别枚举使用多少枚，把所有可能得到的总重量都标记出来。
这个做法能帮助理解题意，但更统一、更标准的写法是把问题改成背包。
题目有 6 种砝码，每种有多枚——这和普通 01 背包有什么不同？
普通 01 背包每个物品独立存在于输入中，每个物品最多选一次。这题每种砝码有多枚相同重量的，本质是多重背包——每个物品类型有数量限制。由于总重 ≤ 1000，直接逐枚展开成 0/1 物品完全可行。
怎么用 DP 表示一个重量是否可称？
设 dp[w] 表示重量 w 能否凑出。初始 dp[0] = true。每加入一枚重量为 value 的砝码，原本能凑出的每个重量，加上这枚砝码后也能凑出。用 bitset 表达：dp |= (dp << value)——一行搞定整轮转移。
为什么用 bitset 而不是普通 bool 数组？
总重 ≤ 1000 很小，普通 bool 数组完全够用。但 bitset 更简洁，dp |= (dp << w) 等价于对 j 从 sum 到 w 倒序做 dp[j] |= dp[j-w]，而且位操作是底层并行，常数极小。
最后 dp.count() 统计可达重量总数，减 1 去掉 dp[0]（一个砝码都不用不算）。
状态表
这张表说明状态的含义：
| 状态 | 含义 |
|---|---|
dp[w] |
重量 w 是否能够被恰好称出 |
从这个定义可以看出，这题状态里存的不是"最大值"或"方案数"，而只是可达性。 这正是背包中的另一类常见状态。
最后统计 1..总重量 中有多少个 dp[w] = true 即可。
DP 公式
设
把每个实际存在的砝码都当作一个 0/1 物品，重量为
最终答案是所有正可达重量的数量：
公式解释：状态只表示某个重量能否被称出。加入一个实际存在的砝码后，原来能称出 w-value 的方案再加上这个砝码，就能称出 w。
代码
本题有两种写法，核心思路完全一致（把每枚砝码展开成 0/1 物品做可达性背包）：
- bitset 位运算（
main.cpp）：dp |= (dp << w)一行完成整轮转移，代码最简洁。 - 普通 bool 数组 + 01 背包倒序（
main-rainboy.cpp）：用两层循环逐枚展开砝码，逆序转移，不依赖位运算，更容易看出转移逻辑。
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-08-08 23:13
* update_at: 2026-08-08 23:13
* 多重背包可行性，bitset
*/
#include <bits/stdc++.h>
using namespace std;
const int maxw = 1005;
int cnt[6];
int w[6] = {1, 2, 3, 5, 10, 20};
bitset<maxw> dp;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
dp[0] = 1;
for (int i = 0; i < 6; ++i) {
cin >> cnt[i];
for (int k = 0; k < cnt[i]; ++k)
dp |= (dp << w[i]);
}
int ans = dp.count() - 1;
cout << "Total=" << ans << "\n";
return 0;
}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-09-06 20:35
* update_at: 2026-09-06 20:35
* 多重可行性背包，01 背包思维（普通 bool 数组）
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005; // 总重量上限
int cnt[6]; // 每种砝码的数量
int w[6] = {1, 2, 3, 5, 10, 20}; // 六种砝码的重量
bool dp[MAXN]; // dp[w] 表示重量 w 是否能被称出
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int sum = 0;
for (int i = 0; i < 6; ++i) {
cin >> cnt[i];
sum += cnt[i] * w[i];
}
dp[0] = true;
// 把每枚砝码看成一个独立的 0/1 物品（重量 = 价值）。逐枚展开后按 01 背包倒序转移。
for (int i = 0; i < 6; ++i)
for (int k = 0; k < cnt[i]; ++k)
for (int j = sum; j >= w[i]; --j)
if (dp[j - w[i]]) dp[j] = true;
int ans = 0;
for (int j = 1; j <= sum; ++j)
if (dp[j]) ++ans;
cout << "Total=" << ans << "\n";
return 0;
}复杂度
- 时间复杂度：
，其中 K是砝码总数，W是总重量 - 空间复杂度：
总结
这题的关键是把"有限个砝码"翻译成"有限个 0/1 物品"。
以后看到"每件东西最多用一次，并且只需要知道哪些和可达"这类条件时，可以优先想到：
- 用布尔数组做可达性背包
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
