指定の金額に対してどの硬貨を何枚出すのかを、LP問題として、PuLPを用いて求めてみる

指定の金額に対してどの硬貨を何枚出すのか(小学生用の計算ドリルに載っていそうな問題)を、LP問題として、PythonライブラリPuLPを用いて求めてみました。

## PuLP

PuLP: Pythonで線形最適化を行うライブラリ。
使用方法は、以下が詳しい。
https://docs.pyq.jp/python/math_opt/pulp.html

## 導入・バージョン確認・import

インストールは、Windowsのコマンドプロンプトを用いて、DOSコマンドでインストールする場合、

```python
python.exe -m pip install pulp
```

Jupyter内でインストールする場合は、

```python
pip install pulp
```

確認すると、

```python
pip show pulp
```

    Name: PuLP
    Version: 2.3
    Summary: PuLP is an LP modeler written in python. PuLP can generate MPS or LP files and call GLPK, COIN CLP/CBC, CPLEX, and GUROBI to solve linear problems.
    Home-page: https://github.com/coin-or/pulp
    Author: J.S. Roy and S.A. Mitchell
    Author-email: pulp@stuartmitchell.com
    License: UNKNOWN
    Location: D:\wpy64-3950\python-3.9.5.amd64\lib\site-packages
    Requires: amply
    Required-by: 
    Note: you may need to restart the kernel to use updated packages.
    
インポートは、

```python
import pulp
```

## 例題を用意
指定の金額に応じて、どの硬貨を何枚出すのかを求める問題を考える。1円玉が5枚、5円玉が4枚、10円玉が3枚、50円玉が2枚あるとして、金額、例えば73円を出す場合、

* 出す硬貨の枚数を最小にする場合 (→最も硬貨を出す手作業を軽減する場合)
* 出す硬貨の枚数を最大にする場合 (→最も財布の中の硬貨を減らす場合)

において、どの硬貨を何枚出すのか、以降で求める。

## 出す硬貨の数を最小にしたい場合


```python
money = 73 # 金額

LP = pulp.LpProblem(sense=pulp.LpMinimize)
yen1 = pulp.LpVariable("1円玉", 0, 5, cat=pulp.LpInteger)
yen5 = pulp.LpVariable("5円玉", 0, 4, cat=pulp.LpInteger)
yen10 = pulp.LpVariable("10円玉", 0, 3, cat=pulp.LpInteger)
yen50 = pulp.LpVariable("50円玉", 0, 2, cat=pulp.LpInteger)
LP += 1*yen1 + 5*yen5 + 10*yen10 + 50*yen50 == money
LP += pulp.lpSum([yen1, yen5, yen10, yen50]) # 合計枚数最小
```


```python
LP.solve()
print("求解の結果:", pulp.LpStatus[LP.status])
```

    求解の結果: Optimal
    


```python
print(f"""金額{money}円には、
  1円玉{pulp.value(yen1):.0f}枚、5円玉{pulp.value(yen5):.0f}枚、
  10円玉{pulp.value(yen10):.0f}枚、50円玉{pulp.value(yen50):.0f}枚""")
```

    金額73円には、
      1円玉3枚、5円玉0枚、
      10円玉2枚、50円玉1枚
    

## 出す硬貨の数を最大にしたい場合


```python
money = 73 # 金額

LP = pulp.LpProblem(sense=pulp.LpMaximize)
yen1 = pulp.LpVariable("1円玉", 0, 5, cat=pulp.LpInteger)
yen5 = pulp.LpVariable("5円玉", 0, 4, cat=pulp.LpInteger)
yen10 = pulp.LpVariable("10円玉", 0, 3, cat=pulp.LpInteger)
yen50 = pulp.LpVariable("50円玉", 0, 2, cat=pulp.LpInteger)
LP += 1*yen1 + 5*yen5 + 10*yen10 + 50*yen50 == money
LP += pulp.lpSum([yen1, yen5, yen10, yen50]) # 合計枚数最大
```


```python
LP.solve()
print("求解の結果:", pulp.LpStatus[LP.status])
```

    求解の結果: Optimal
    


```python
print(f"""金額{money}円には、
  1円玉{pulp.value(yen1):.0f}枚、5円玉{pulp.value(yen5):.0f}枚、
  10円玉{pulp.value(yen10):.0f}枚、50円玉{pulp.value(yen50):.0f}枚""")
```

    金額73円には、
      1円玉3枚、5円玉4枚、
      10円玉0枚、50円玉1枚
    

## 得られた結果
金額73円は、

* 1円玉3枚、5円玉0枚、10円玉2枚、50円玉1枚、の最小6枚で作ることが出来、また、
* 1円玉3枚、5円玉4枚、10円玉0枚、50円玉1枚、の最大8枚で作ることが出来る。


## 手持ちの硬貨の枚数を倍にした場合

1円玉が5枚、5円玉が4枚、10円玉が3枚、50円玉が2枚あったものから、
1円玉が10枚、5円玉が8枚、10円玉が6枚、50円玉が4枚に条件を変えて、再度、以降で求めてみる。

## 出す硬貨の数を最小にしたい場合


```python
money = 73 # 金額

LP = pulp.LpProblem(sense=pulp.LpMinimize)
yen1 = pulp.LpVariable("1円玉", 0, 10, cat=pulp.LpInteger)
yen5 = pulp.LpVariable("5円玉", 0, 8, cat=pulp.LpInteger)
yen10 = pulp.LpVariable("10円玉", 0, 6, cat=pulp.LpInteger)
yen50 = pulp.LpVariable("50円玉", 0, 4, cat=pulp.LpInteger)
LP += 1*yen1 + 5*yen5 + 10*yen10 + 50*yen50 == money
LP += pulp.lpSum([yen1, yen5, yen10, yen50]) # 合計枚数最小
```


```python
LP.solve()
print("求解の結果:", pulp.LpStatus[LP.status])
```

    求解の結果: Optimal
    


```python
print(f"""金額{money}円には、
  1円玉{pulp.value(yen1):.0f}枚、5円玉{pulp.value(yen5):.0f}枚、
  10円玉{pulp.value(yen10):.0f}枚、50円玉{pulp.value(yen50):.0f}枚""")
```

    金額73円には、
      1円玉3枚、5円玉0枚、
      10円玉2枚、50円玉1枚

同じ結果となる。

## 出す硬貨の数を最大にしたい場合


```python
money = 73 # 金額

LP = pulp.LpProblem(sense=pulp.LpMaximize)
yen1 = pulp.LpVariable("1円玉", 0, 10, cat=pulp.LpInteger)
yen5 = pulp.LpVariable("5円玉", 0, 8, cat=pulp.LpInteger)
yen10 = pulp.LpVariable("10円玉", 0, 6, cat=pulp.LpInteger)
yen50 = pulp.LpVariable("50円玉", 0, 4, cat=pulp.LpInteger)
LP += 1*yen1 + 5*yen5 + 10*yen10 + 50*yen50 == money
LP += pulp.lpSum([yen1, yen5, yen10, yen50]) # 合計枚数最大
```


```python
LP.solve()
print("求解の結果:", pulp.LpStatus[LP.status])
```

    求解の結果: Optimal
    


```python
print(f"""金額{money}円には、
  1円玉{pulp.value(yen1):.0f}枚、5円玉{pulp.value(yen5):.0f}枚、
  10円玉{pulp.value(yen10):.0f}枚、50円玉{pulp.value(yen50):.0f}枚""")
```

    金額73円には、
      1円玉8枚、5円玉7枚、
      10円玉3枚、50円玉0枚

枚数がかなり増加する。

## 得られた結果
(1円玉が10枚、5円玉が8枚、10円玉が6枚、50円玉が4枚の場合)、金額73円は、

* 1円玉3枚、5円玉0枚、10円玉2枚、50円玉1枚、の最小6枚で作ることが出来、また、
* 1円玉8枚、5円玉7枚、10円玉3枚、50円玉0枚、の最大18枚で作ることが出来る。

(小学生の頃、変数の数が数個で＆条件式は1つだけですが、簡単なLP問題を、皆解いていたということか... いや違うか... 単にスケール可能な問題としてコンピュータで解く場合はこうなりますということか。)