CSP-J 入门级 · CSP 2026 入门级第一轮 第 10 题

【单选】某国硬币面值为 1 元、4 元、6 元且数量不限，凑出 9 元最少需要多少枚（ ）。

面值是 1、4、6，凑 9 元。先试大面值：6+1+1+1 用 4 枚，4+4+1 只用 3 枚——枚举时按"用几枚 6 元"分类即可。

贪心地认为"面值越大越好"直接用 6+... 得 4 枚，忽略 4+4+1；也容易误以为 9 元只能由 6+3 组合（3 元不存在）。

解析

本题考查贪心法的局限与最优解验证（凑硬币最少枚数）。

直接枚举（面值 6 元的枚数分类）

最优方案：4 + 4 + 1 = 9，共 3 枚，选 A。

为什么"贪心"在这里会出错

若按"每次尽量选最大面值"的贪心策略：9 → 选 6（剩 3）→ 选 1,1,1，得到 4 枚。 而最优解 3 枚却没有使用最大的 6 元面值。这说明：这套面值（1、4、6）不满足"贪心可解"的结构，只能老实地枚举或动态规划。

拓展：动态规划的思路

设 dp[x] = 凑出 x 元的最少硬币数，dp[0] = 0，转移：

dp[x] = 1 + min(dp[x−1], dp[x−4], dp[x−6])（下标非负才有意义）

算到 dp[9]：dp[1]=1, dp[2]=2, dp[3]=3, dp[4]=1, dp[5]=2, dp[6]=1, dp[7]=2, dp[8]=2（4+4）, dp[9]=min(dp[8],dp[5],dp[3])+1 = min(2,2,3)+1 = 3 ✓ 与枚举一致。

记忆点

• 硬币问题里"贪心能用"需要面值体系满足特殊性质（如 1、5、10、25 这类规范体系），缺一个中间面值就可能破功；
• 考场遇到小规模（凑 9 元）直接分类枚举比推导更快。