ARTICLE · 1108894
2026武汉青少年程序设计竞赛真题:多重背包解析
2026武汉青少年程序设计竞赛真题:多重背包解析
3 10 3 4 2 4 5 1 2 3 3 
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int N, W; if (!(cin >> N >> W)) return 0; vector<long long> dp(W + 1, 0); // dp[j]: 容量 j 下的最大价值 for (int i = 0; i < N; i++) { int w, v, c; cin >> w >> v >> c; for (int k = 1; c > 0; k <<= 1) { // 二进制拆分 int take = min(k, c); // 本块件数 int bw = w * take, bv = v * take; // 块的「打包」重量与价值 for (int j = W; j >= bw; j--) // 0/1 背包：一维逆序 dp[j] = max(dp[j], dp[j - bw] + bv); c -= take; } } cout << dp[W] << endl; return 0; } def solve(items, W): dp = [0] * (W + 1) for w, v, c in items: k = 1 while c > 0: take = min(k, c) bw, bv = w * take, v * take for j in range(W, bw - 1, -1): # 一维逆序 if dp[j - bw] + bv > dp[j]: dp[j] = dp[j - bw] + bv c -= take k <<= 1 return dp[W] # 样例 items = [(3, 4, 2), (4, 5, 1), (2, 3, 3)] print(solve(items, 10)) # -> 14 
2026武汉青少年程序设计竞赛真题：多重背包解析
🎒 赛前特训｜2026 武汉青少年程序设计竞赛（C++ 算法赛项）注重考察资源分配类动态规划。今天我们用一道原创「真题」拆解多重背包问题，并给出二进制拆分优化的完整解法与对拍验证。
一、题目背景
校园科技节义卖摊位要备货：一共有 N 种纪念品，第 i 种单件重量 w[i]、价值 v[i]，仓库里最多有 c[i] 件。你有一个最大承重 W 的背包，问在不超过承重的前提下，能装下的纪念品总价值最大是多少？
二、输入与输出
输入：第一行 N W；接下来 N 行每行 w v c。输出：一个整数，最大总价值。
样例输入：
样例输出：14（取 3 件第三种 + 1 件第二种：重量 6+4=10，价值 9+5=14）。
三、二进制拆分优化思路
朴素做法把第 i 种拆成 c[i] 个相同的 0/1 物品，再跑 0/1 背包，复杂度 O(N·W·Σc)，当 c[i] 很大时会超时。
关键优化：把数量 c[i] 按二进制拆成 1, 2, 4, … , 2^k, 余数 这些「组合块」。例如 c=13 拆成 1,2,4,6：任意 0..13 的件数都能由这些块唯一拼出（这正是二进制的思想）。每块作为一个新物品，重量为 w[i]·块、价值为 v[i]·块。拆分后物品数降到 O(Σlog c[i])，再跑标准 0/1 背包（一维数组逆序更新）即可。
时间复杂度 O(N·W·log(max c))，远优于朴素拆分；空间复杂度 O(W)（一维 DP 数组）；正确性基础：二进制表示可拼出 0..c 的任意整数，不漏不重。
四、C++ 参考代码
五、Python 参考代码
六、复杂度与边界
时间 O(N·W·log(max c))；空间O(W)；重量/价值可能很大，价值建议用 long long（C++）或 Python 大整数；c=0的件数直接跳过； w>W的块不会被选中（逆序循环自然排除）；逆序更新是 0/1 背包命门，顺序会变成完全背包，务必注意。
七、考点拆解（7 点）
- 背包模型识别
：每件物品有「数量上限」，是多重背包而非 0/1 / 完全背包； - 二进制拆分
：用 2 的幂块拼出 0..c 任意件数，把多重背包压成 0/1 背包； - 0/1 背包一维 DP
：状态 dp[j]表示容量 j 最大价值，逆序更新防重复选； - 打包思想
：块的「重量/价值」按比例放大，等价于一整组同款物品； - 余数处理
：最后一块取 min(k, c)，避免超出原数量； - 数据类型
：重量乘积可能溢出 int，价值用 64 位； - 复杂度权衡
：把 O(N·W·Σc) 降到 O(N·W·log c)，理解「拆分」带来的指数级加速。
八、动手练一练
把样例改成 N=4, W=15，物品 (2,3,4) (5,6,2) (3,4,3) (1,2,5)，最大价值是多少？欢迎在评论区贴出你的运行结果，下期拆解「单调队列优化多重背包」。
📚 免费少儿编程资料（夸克网盘领取）
以下资料来自夸克网盘分享。个人号链接暂不支持直接点击，请长按或复制下方链接，打开夸克网盘 App / 网页粘贴即可保存：
1. 全国青少年信息素养大赛复赛集训题目Python&C++.docx https://pan.quark.cn/s/93995d3cb150 2. 2024信息素养-智能算法应用挑战赛-复赛初中组题目7月7日.pdf https://pan.quark.cn/s/da97b5dbf75d 3. Python背记手册.pdf https://pan.quark.cn/s/7568ae9ca92b 4. Python课程 https://pan.quark.cn/s/a94bf02d00c6 5. 2024信息素养大赛图形化复赛集训题答案3-9 https://pan.quark.cn/s/6ccab7ec3cbc 6. 2025年03月份电子学会考级真题 https://pan.quark.cn/s/4403c4228912 7. 2025全国青少年信息素养大赛赛项说明 https://pan.quark.cn/s/d9d0df4a9f29 8. 青少儿信息素养大赛编程资料 https://pan.quark.cn/s/4ab6bd83be8a
资料持续更新，关注本号第一时间获取新分享。