財布の中の小銭最小化問題

はじめに

財布の小銭最少化問題の極北〜694円の会計に1245円出す人〜が大分前に話題になっていたので、線形計画問題として解けるようにした。Pythonだとモデリングライブラリとしてpulpが使えるため、pulpを利用。pulpの使い方がいまいちという方のために、以下の記事をリンクしておきます。
PuLP による線型計画問題の解き方ことはじめ

ソース

694円の商品に1245円出すことを確認。
下記ソースのコメントを見れば、やっていることは理解出来るかと思います。
支払い変数とお釣り変数の2種類を使ってますが、実は支払い後の財布の枚数変数の1種類で事足りることに気づきました。定式化のセンスが問われるところですなー。大規模問題になるとここらへんが命取りになります。
あと、財布の中身の枚数は硬貨・紙幣で区別していません。枚数最小化ではなく体積最小化がベターですね。
【追記】
しっかり研究している人がいるもんですな。
財布の中の小銭の最適化について

MinimizeChange.py

import pulp
import numpy as np
#お金の種類
money_type = (10000, 5000, 2000, 1000, 500, 100, 50, 10, 5, 1)
#商品の金額
price = 694
#財布の中身（左から10000の枚数、5000の枚数、...）
purse = [1, 1, 1, 1, 0, 4, 0, 4, 1, 3]

#最小化の問題を作りましょう...
problem = pulp.LpProblem('Change Minimization', pulp.LpMinimize)
#何円硬貨を何枚使うか変数
pay_var = np.array([pulp.LpVariable('pay_var_'+str(i),0,purse[k]+1,'Integer') for k,i in enumerate(money_type)])
#何円硬貨が何枚お釣りとして返ってくるか変数
change_var = np.array([pulp.LpVariable('change_var_'+str(i),0,purse[k]+1,'Integer') for k,i in enumerate(money_type)])

'''
目的関数
会計後の財布の中身のお札・硬貨枚数 + 払うお札・硬貨枚数 * 0.01
後ろの項は、10000円払って10000円お釣り返してもらう的な意味不明な結果を避けるため
'''
problem += pulp.lpSum(purse - pay_var + change_var) + pulp.lpSum(pay_var)*0.01

#払ったお金は商品金額より大きくないと駄目よん制約
problem += pulp.lpDot(money_type,pay_var) - price >= 0
#お釣り金額＝10000*10000枚数+5000*5000枚数+...+1*1枚数じゃなきゃいけないよ制約
problem += pulp.lpDot(money_type,change_var)  == pulp.lpDot(money_type,pay_var) - price
#財布の中の枚数より多くは支払えないよん制約
for i,v in enumerate(purse):
    problem += pay_var[i] - purse[i] <= 0
status = problem.solve()

print("最適な支払方法")
for i,v in enumerate(pay_var):
    print("{}円　{}枚".format(money_type[i],pay_var[i].value()))
print("お釣り枚数")
for i,v in enumerate(change_var):
    print("{}円　{}枚".format(money_type[i],change_var[i].value()))

応用

中の硬貨・紙幣をカウント出来る財布があれば、会計の度に支払い金額をレコメンド出来るのですが。時代に逆行している感半端ないですが、そんな財布あったらひとまず買うけどな（笑）ご興味ある方はトライを！