Edited at

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

More than 3 years have passed since last update.


はじめに

財布の小銭最少化問題の極北〜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()))



応用

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