硬貨の組み合わせ問題（貪欲法の簡単な例題）

貪欲法や欲張り法（greedy algorithm, greedy strategy）と呼ばれるアルゴリズムの話。

このアルゴリムのよく知られた例は、ある金額を実現する硬貨の組合せの中で枚数が最も少ないものを求める問題。たとえば「765円のお釣を払う場合、500円硬貨1枚、100円硬貨2枚、50円硬貨1枚、10円硬貨1枚、5円硬貨1枚の計6枚」という結果は「高額の硬貨から順番に使って払う」ことによって求まる。「高い硬貨から使っていくという点で『欲張り』」らしい。

とても分かりやすいアルゴリズムである反面、局所的に最善の選択を繰り返すに過ぎないので、条件次第では最適解が求まらないこともある。

以下はこの問題を解く具体的な例だが、1円玉から500円玉のそれぞれについて枚数に制限を加えた形になっている。また、Elispなので金額と枚数の組を表すのに連想リスト（association list）を使っている。

;;; 引数は、金額と、利用可能な硬貨を表す連想リスト（金額と枚数）
(defun solve (yen coins)
  (if (zerop yen) nil
    (let ((n (min (/ yen (caar coins))
                  (cdar coins) )))
      (cons (cons (caar coins) n)
            (solve (- yen (* n (caar coins)))
                   (cdr coins) )))))

;;; 例1.
;;; 金額: 765円、
;;; 使える硬貨: 500円*1、100円*1、50円*3、10円*3、5円*3、1円*3
(solve 765 '((500 . 1) (100 . 1) (50 . 3) (10 . 3) (5 . 3) (1 . 3)))
=> ((500 . 1) (100 . 1) (50 . 3) (10 . 1) (5 . 1))

;;; 例2.
;;; 金額: 623円、
;;; 使える硬貨: 500円*0、100円*5、50円*3、10円*1、5円*2、1円*5
(solve 623 '((500 . 0) (100 . 5) (50 . 3) (10 . 1) (5 . 2) (1 . 10)))
=> ((500 . 0) (100 . 5) (50 . 2) (10 . 1) (5 . 2) (1 . 3))

参考

• Algorithms with Python / 欲張り法
• Amazon.co.jp： プログラミングコンテストチャレンジブック: 秋葉 拓哉, 岩田 陽一, 北川 宜稔: 本