---
title: 问题求解：硬币找零问题的 Kozen-Zaks 条件
author: Licphel
date: 2026-06-15 18:16:21
---

## 引言

硬币找零问题是一个经典的算法入门案例。

通常我们会这样描述它：给定几种面额的硬币，要凑出某个金额，如何用最少数量的硬币？

直觉告诉我们：每次尽量用最大面额的硬币。这个策略就是贪心算法。

对于人民币面额，贪心策略确实总是正确的。但如果我们虚构一种 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$，贪心算法给出的硬币数都是最优解，那么贪心算法就是全局最优的。

---

All rights reserved by Licphel.
Original: https://ntopia.top/posts/问题求解-硬币找零问题的-kozen-zaks-条件-1781547382050