おつりの話

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

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

## 問題

- 硬貨とお札は 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]という記事があります。そこでは、

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

- おつりの話
- おつり問題の定式化
- 動的計画法による最適解の計算
- 分子限定法による最適解の計算
- 欲張り法による近似解
- むすび[^2]

[^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$

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

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

```py3: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

持ち金を[ネタ元](https://togetter.com/li/916958)と同じにして、694円の買い物をしてみます。

```py3: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円の買い物をしてみます。

```py3: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

```py3: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

```py3:python
SolveChange2(694, [3,1,4,0,4,0,1,0])
>>>
価格	  694円
支払い	 1245円
 1000円 100円×2 10円×4 5円
おつり	  551円
 500円 50円 1円
```

### 例題B

```py3:python
SolveChange2(499, [2,1,5,0,4,1,2,0])
>>>
価格	  499円
支払い	  550円
 500円 10円×5
おつり	   51円
 50円 1円
```

同じ答えになりました。

## 最後に

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

## 参考

- [組合せ最適化を使おう - Qiita](https://qiita.com/SaitoTsutomu/items/bfbf4c185ed7004b5721)
- [最適化におけるPython - Qiita](https://qiita.com/SaitoTsutomu/items/070ca9cb37c6b2b492f0)
- [お釣りの枚数を計算する - Qiita](https://qiita.com/SaitoTsutomu/items/ae0b08283373a7a2f170)
- [釣銭最適化問題 ～より現実的な問題に～ - Qiita](https://qiita.com/RyuSA/items/8c5f262ddb145bc60d51)
- [財布の中の小銭最小化問題 - Qiita](https://qiita.com/shinji071/items/560c0197ef4c72abca55)
- [欲張り法](http://www.orsj.or.jp/~wiki/wiki/index.php/%E6%AC%B2%E5%BC%B5%E3%82%8A%E6%B3%95)