引言
硬币找零问题是一个经典的算法入门案例。
通常我们会这样描述它：给定几种面额的硬币，要凑出某个金额，如何用最少数量的硬币？
直觉告诉我们：每次尽量用最大面额的硬币。这个策略就是贪心算法。
对于人民币面额，贪心策略确实总是正确的。但如果我们虚构一种 Arcadia 币，其面值分别是 ${1, 3, 4}$，要凑 $6$ 元：贪心会选 $4+1+1$，但最优解是 $3+3$。贪心失败了。
那么问题来了：什么样的硬币系统，贪心算法能保证最优？
这就引出了 Kozen–Zaks 条件。
什么是 Canonical 硬币系统？
学术上，如果一个硬币系统能让贪心算法对任意金额都给出最优解，这个系统被称为 canonical（典范的）硬币系统。人民币、美元都是 canonical 系统。而 Arcadia 币不是。
Kozen–Zaks 条件的核心思想
Dexter Kozen 和 Shmuel Zaks 在 1994 年的论文中给出了一个重要的理论成果：
如果存在反例（贪心非最优的金额），那么最小的反例一定落在某个有限的区间内。
具体来说，设硬币面额为：
$$
1 = c_1 < c_2 < c_3 < \dots < c_m
$$
那么最小的反例 $x$ 满足：
$$
c_3 + 1 < x < c_{m-1} + c_m
$$
这个区间上界是 $c_{m-1} + c_m$——第二大的硬币加上最大的硬币。以 ${1,3,4}$ 为例，$c_{m-1} + c_m = 3+4=7$，而最小反例 $6$ 确实小于 $7$。
验证方法
Corollary：如果对于区间 $(c_3+1,\ c_{m-1}+c_m)$ 内的每个金额 $x$，贪心算法给出的硬币数都是最优解，那么贪心算法就是全局最优的。
