アリ本​「硬貨の問題」の​考察

いわゆるアリ本¹で、非常に日常的な問題の解法として貪欲法が紹介されていた が、なぜ貪欲法で厳密解が求まるのかわからなかったので考えてみた。

硬貨の問題

１円玉、５円玉、１０円玉、５０円玉、１００円玉、５００円玉が、それぞれ C₁, C₅, C₁₀, C₅₀, C₁₀₀, C₅₀₀枚ずつあります。できるだけ少ない枚数の 硬貨でＡ円を支払いたいと考えています。何枚の硬貨を出す必要があるでしょ うか？なお、そのような支払い方は少なくとも１つは存在するとします。²

まず、Ａ円を最少の硬貨で払う問題は、①Ａ円以下で（手持ちの硬貨のある）最 大の額面金額Ｂを最少の硬貨で払う問題と、②（Ａ－Ｂ）円を最少の硬貨で払う問 題に分割できます。

なぜかと言うと、Ａ円を払う硬貨の組み合わせは、設定された額面金額の性質 （ある額面についてそれより小さな額面に、約数でない物が存在しない）から、 必ずちょうどＢ円になる部分を含むからです。

Ａ円になる硬貨の任意の組み合わせを大きい硬貨から並べて、足した金額がＢ 円以上になったところで辞める事にします。そうするとどのような額面金額Ｃ の硬貨が足された時にＢ円以上になったとしても、その直前の金額はＣ円玉か、 それよりも大きな（Ｃの倍数額面の）硬貨０枚以上で成り立っているので、Ｃ の倍数になります。したがって、実はＣ円玉を足す直前の金額は（Ｂ－Ｃ）円 で、Ｂ円以上というのはちょうどＢ円だったことになります。

Ｂ円を払う最少の硬貨の組み合わせはＢ円玉１つからなることは自明ですから、 これが１つ目の部分問題に対する最適解になります。

Ａ円を払う最少の硬貨の組み合わせがＢ円玉を含まなかったとしたらどうでしょ うか？ 先の議論から、そのような組み合わせはちょうどＢ円になる部分を含 むことになります。しかし、これはＢ円玉１つで置き換えて、全体の枚数を少 なくすることができます。（この置き換えはＢ円玉以外を使いませんので、他の 部分の実現可能性に影響しませんから、常に可能です。）

最少の硬貨の組み合わせのはずだったのに、より少ない硬貨の組み合わせを作 ることができてしまいました。よって、Ｂ円玉を含まない最少の硬貨の組み合 わせは存在せず、額面金額Ｂの硬貨がある場合、Ａ円を払う最少の硬貨の組み 合わせはそのＢ円玉を含みます。

Ａ円を最少の硬貨で払う問題の最適解が、Ｂ円を最少の硬貨（つまりＢ円玉１ 枚）で払う問題と、（Ａ－Ｂ）円を最少の硬貨で払う問題のそれぞれの最適解 から成り立っていることになります。よって、部分問題最適性が満たされるこ とになり、繰り返し「Ｂ円」を選ぶ貪欲法で厳密解が求まることがわかります。

多分こんな感じ。