More than 1 year has passed since last update.


なるべく財布を軽くしておきたい人のために

キャッシュで買い物をしていると、おつりが出るときがありますが、なるべく財布を軽くするには、どのように支払ったらよいかを考えて見ます。


問題


  • 硬貨とお札は 1,5,10,50,100,500,1000,5000,10000 とし、重さは 1,3.75,4.5,4,4.8,7,1,1,1 (グラム)とします。


  • 1万円は十分にあるとします。


  • 財布には、それぞれ初期個数ずつあり、金額 price 円の買い物をし、お金を払います。おつりを返す人は、あなたの財布が最も軽くなるように、おつりを返します。


  • 財布の重さを最小化するには、どのように払えばよいでしょうか?



参考情報

現代数学社の Basic数学(1992年4月号)に、茨木俊秀先生の「楽しく学ぶOR教室 整数計画法I」1という記事があります。そこでは、


  • おつりの話

  • おつり問題の定式化

  • 動的計画法による最適解の計算

  • 分子限定法による最適解の計算

  • 欲張り法による近似解

  • むすび2

と7ページにわたって、おつりの話が、詳しく説明されています。

ここでは、定式化してソルバーで解いてみましょう。


考え方その1


集合

$ N=\{0,1, \cdots, 8\}$ … 添え字

$ P=\{1,5,10,50,100,500,1000,5000,10000\} = \{p_i | i \in N\} $ … 金額

$ \mathbb{N} $ … 0以上の整数の集合


定数

$ \mbox{price} $ … 価格

$ \mbox{ini}=\{c_i | i \in N\} $ … 初期個数

$ \mbox{weight}=\{w_i | i \in N\} $ … 重さ


変数

$ X=\{x_i \in \mathbb{N} | i \in N\} $ … 支払い個数

$ Y=\{y_i \in \mathbb{N} | i \in N\} $ … おつり個数


定式化その1

最小化
$\sum_i{(\epsilon x_i - w_i x_i + w_i y_i)} ~~ $ 3

制約条件
$ x_i \le c_i ~~~~ \forall i \in N $

$ \sum_i{p_i (x_i - y_i)} = \mbox{price} $

$ x_i \in \mathbb{N}, ~~~ y_i \in \mathbb{N} ~~~ \forall i \in N$


Pythonによるプログラムその1


python

import numpy as np

from pulp import LpProblem, LpInteger, lpDot, lpSum, value
from ortoolpy import addvars
P = [1,5,10,50,100,500,1000,5000,10000]
W = [1,3.75,4.5,4,4.8,7,1,1,1] # 重さ
def ShowResult(price, rx, ry):
print('価格\t%5d円\n支払い\t%5d円'%(price,rx@P))
for i in range(8,-1,-1):
if rx[i]:
print(' %d円'%P[i], end='')
if rx[i]>1:
print(%d'%rx[i], end='')
print('\nおつり\t%5d円'%(ry@P))
for i in range(8,-1,-1):
if ry[i]:
print(' %d円'%P[i], end='')
if ry[i]>1:
print(%d'%ry[i], end='')
def SolveChange1(price, ini):
assert len(ini)==8
ini.append(max(0,(price-np.dot(P[:8],ini)+9999)//10000))
m = LpProblem()
X = addvars(9, cat=LpInteger)
Y = addvars(9, cat=LpInteger)
m += 1e-4*lpSum(X) - lpDot(W,X) + lpDot(W,Y)
for i in range(9):
m += X[i] <= ini[i]
m += lpDot(P,X) - lpDot(P,Y) == price
m.solve()
rx,ry = np.vectorize(value)(X),np.vectorize(value)(Y)
ShowResult(price, rx, ry)


例題A

持ち金をネタ元と同じにして、694円の買い物をしてみます。


python

SolveChange1(694, [3,1,4,0,4,0,1,0])

>>>
価格 694
支払い 1245
1000 100円×2 10円×4 5
おつり 551
500 50 1

同じように、1245円払いました。


例題B

499円の買い物をしてみます。


python

SolveChange1(499, [2,1,5,0,4,1,2,0])

>>>
価格 499
支払い 550
500 10円×5
おつり 51
50 1

軽くするために、10円*5 を 50円に両替してもらっています。


考え方その2

そもそも最軽量になった「おつりをもらった後」の状態さえわかれば、減った分=支払った個数、増えた分=おつりの個数、と計算できます。

やってみましょう。


変数

$ Z=\{z_i \in \mathbb{N}| i \in N\} $ … 最後の個数


定式化その2

最小化
$\sum_i{w_i z_i} $

制約条件
$ \sum_i{p_i (c_i - z_i)} = \mbox{price} $

$ z_i \in \mathbb{N} ~~~ \forall i \in N$


Pythonによるプログラムその2


python

def SolveChange2(price, ini):

assert len(ini)==8
ini.append(max(0,(price-np.dot(P[:8],ini)+9999)//10000))
m = LpProblem()
Z = addvars(9, cat=LpInteger)
m += lpDot(W,Z)
m += lpDot(P,ini) - lpDot(P,Z) == price
m.solve()
rz = ini-np.vectorize(value)(Z)
rx = np.max([[0]*9,rz], 0) # 減った分
ry = np.max([[0]*9,-rz], 0) # 増えた分
ShowResult(price, rx, ry)


例題A


python

SolveChange2(694, [3,1,4,0,4,0,1,0])

>>>
価格 694
支払い 1245
1000 100円×2 10円×4 5
おつり 551
500 50 1


例題B


python

SolveChange2(499, [2,1,5,0,4,1,2,0])

>>>
価格 499
支払い 550
500 10円×5
おつり 51
50 1

同じ答えになりました。


最後に

考え方その2で 定式化はシンプルになりましたが、今回のような金額の場合、ソルバーで解くまでもなく、(大きい方から)欲張り法で厳密解が得られます。

(金額が任意の場合の欲張り法は、近似解になります)


参考





  1. 最近では、整数計画法のことを整数最適化と呼ぶようになってきています。 



  2. 茨城先生は、「おつり枚数の少なくなる金額の種類は何か」についても考えていてました。 



  3. $\epsilon$をつけて、変数 X を無駄に増やさないようにする。