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

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

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

↓

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

↓

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

↓

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