CSP-S 2020 第一轮 第6题：下列哪些问题不能用贪心法精确求解？（

题目

下列哪些问题不能用贪心法精确求解？（  ）

选项

• A. 霍夫曼编码问题
• B. 0-1 背包问题
• C. 最小生成树问题
• D. 单源最短路径问题

答案

B

题解

答案通常选 B．0-1 背包问题。

贪心法每一步都选择当前最优方案，但只有当这些局部选择能保证整体最优时，才能精确求解。

• A．霍夫曼编码：每次合并权值最小的两个节点，是贪心算法，能得到最优编码。
• B．0-1 背包：每件物品只能完整地选或不选，按价值、重量或单位重量价值贪心，都不能保证最优。
• C．最小生成树：Prim 和 Kruskal 都是贪心算法，能得到最优解。
• D．单源最短路径：在边权非负时，Dijkstra 算法可以用贪心法精确求解。

例如，背包容量为 4，三件物品的“重量、价值”分别是 (3, 5)、(2, 3)、(2, 3)。按单位重量价值贪心，会先选第一件，总价值为 5；但选后两件，总价值为 6，更优。

注意：题目没有说明边权条件，表述不够严谨；按通常考查意图选 B，但有负权边时 Dijkstra 不保证正确。