CSP-S 2025 第一轮 第9题：一个 0-1 背包问题，背包容量为 20。现有 5 个物品，其重量和价值分别为

题目

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

选项

• A. $43$
• B. $41$
• C. $45$
• D. $44$

答案

D

题解

选 D．\(44\)。

可以用“从全部物品中去掉一些”的思路：

• 全部物品总重量为 \(7+5+4+3+6=25\)，总价值为 \(56\)。
• 背包容量为 \(20\)，所以至少要去掉重量为 \(5\) 的物品。
• 若只去掉一件，可去掉重量为 \(7、5、6\) 的物品，其中损失价值最小的是重量为 \(5\)、价值为 \(12\) 的物品。
• 若去掉两件或更多，损失价值至少为 \(7+9=16\)，不如只去掉价值为 \(12\) 的那件。

因此，选第 \(1、3、4、5\) 件，重量恰好为 \(20\)，最大总价值为 \[ \boxed{15+9+7+13=44}. \]