This page is a personal scratchpad.

以前書いた、「財布の小銭を最小限に抑える支払い方の求め方」について考えてみた。

ここでは仮に "「1」のつく小銭が 4 枚以下、「5」の付く小銭が 1 枚以下となっている状態" のことを「最適化されている」と表現する。自分の手持ちの小銭は既に最適化されていて、なおかつ小銭も必ず最適化された状態で戻ってくると仮定した上で、手持ち額以内のどんな支払額に対しても、返ってきた小銭と手持ち合わせて最適化されている状態を維持出来るような支払い方の求め方だ。

手持ちの小銭の中で、支払額以上かつ支払額との差が最も少ない小銭の組み合わせで仮に支払った場合、戻ってくるお釣りについて以後考える

↓

可能であれば、お釣りの 1 円玉と合わせて 5 枚になるよう、手持ちの 1 円玉を支払う。その結果、お釣りの 1 円玉 5 枚が 5 円玉 1 枚に繰り上がる。

↓

可能であれば、お釣りの 5 円玉と合わせて 2 枚になるよう、手持ちの 5 円玉を支払う。その結果、お釣りの 5 円玉 2 枚は 10 円玉に繰り上がる。

↓

(以後五千円札まで繰り返す)