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

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

問題

  • 硬貨とお札は 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 を無駄に増やさないようにする。