CSP-S 提高级 · CSP 2025 提高级第一轮 第 9 题

一个 $0-1$ 背包问题，背包容量为 $20$。现有 $5$ 个物品，其重量和价值分别为 $7, 5, 4, 3, 6$ 和 $15, 12, 9, 7, 13$。装入背包的物品能获得的最大总价值是多少？

这道题考0-1背包。别急着贪心算性价比，容量只有20，物品数才5个，直接枚举所有组合或套用标准DP都能秒杀。

最容易掉进贪心的坑：按性价比（价值/重量）排序选，本题里性价比最高的是物品1（15/7≈2.14），接着是物品5（13/6≈2.17）。若按性价比选，先拿1和5（重13，值28），再拿物品2（重5，总重18，值40），此时容量剩2，放不下了，总价值40，这就错了。还有人会漏掉物品4，只盯着大件，其实小件凑出来的组合往往更优。

考点与概念

本题核心是0-1背包：给定容量C和n个物品（每个要么选要么不选），求最大总价值。标准解法是用DP：dp[j]表示容量j能装的最大价值，转移方程为dp[j]=max(dp[j], dp[j-w[i]]+v[i])，内层j必须倒序遍历，防止同一物品被重复选取。

命题视角

命题人爱在这里挖两个坑：一是诱导你用贪心（按性价比选），但0-1背包贪心只能得到近似解；二是数据范围看似小，容易让人以为要写复杂代码，其实枚举或DP都很快。

思考心法与推导

拿到题先看容量20和物品数5，直觉是：组合数C(5,4)=5种4件组合、C(5,3)=10种3件组合……总共也就几十种情况，直接枚举最稳妥，还能顺便验证DP结果。

枚举关键组合（重量≤20）：

• 选{1,2,3,4}：重7+5+4+3=19，值15+12+9+7=43
• 选{1,3,4,5}：重7+4+3+6=20，值15+9+7+13=44
• 选{2,3,4,5}：重5+4+3+6=18，值12+9+7+13=41
• 选{1,2,3,5}：重22>20，超重
• 选{1,2,4,5}：重21>20，超重
• 选{1,2,5}：重18，值38；选{1,3,5}：重17，值37；选{1,4,5}：重16，值35；选{2,3,5}：重14，值34；选{2,4,5}：重14，值32；选{3,4,5}：重13，值31。

显然最大值是44，对应物品1、3、4、5。

避坑指南

别贪心！按性价比排序会先拿1和5，再拿2，结果剩2容量放不进任何物品，总价值40，错选A或B。还有人会忽略小件4，只盯着大件，导致漏掉最优解。记住：0-1背包必须用DP或枚举，贪心只在分数背包（可分割）里成立。

考频与趋势

题库里“经典DP模型”只考过1题（2025 CSP提高级），而“背包DP”共考8题，覆盖2018-2026年，其中2025年就有2题（CSP提高级1题、GESP六级1题），2026年也有1题。说明背包DP是高频考点，且近年在CSP提高级和GESP六级中持续出现。

预测

基于2025年2题、2026年1题的分布，未来两年背包相关题目大概率仍会保留，可能继续以单选题形式考查最优解计算，或转为小规模数据要求手写DP流程。暂无足够依据预测具体题型变化，但“不能贪心”这一坑点几乎年年会考。