ポケコインを効率よく買いたいので整数計画問題に落とし込む

Pokemon Goを始めた。 最初のポケモンはピカチュウであった。 卵を複数入手し、10kmという長距離を歩かされるものもあり、インキュベーターは複数あった方が効率がよさそうだなと思い、初めてGoogle Playカードを買った。 1500円である。 いざチャージしたお金をポケコインに換金しようとすると、1円1コインではなく一度に換金するコインの量によって変わることがわかった。

さて、どのように買えば効率よく買えるのだろうか。パッと見、貪欲戦略で解決しそうな気がしないでもないが、整数計画問題に落とし込めば近似解ぐらいは得られそうである。 Pythonでは、SciPyかPuLPが線型計画問題のライブラリを備えているようなので、簡単にかけそうなPuLPで解いてみた。

import pulp

# Google Playの残金額
amount_of_money = 1500

# 線型計画問題の定義
problem = pulp.LpProblem('PokeCoinMaximised', pulp.LpMaximize)
x_1 = pulp.LpVariable('100pokecoin', 0, 10, 'Integer') 
x_2 = pulp.LpVariable('550pokecoin', 0, 10, 'Integer') 
x_3 = pulp.LpVariable('1200pokecoin', 0, 10, 'Integer') 
x_4 = pulp.LpVariable('2500pokecoin', 0, 10, 'Integer') 
x_5 = pulp.LpVariable('5200pokecoin', 0, 10, 'Integer') 
x_6 = pulp.LpVariable('14500pokecoin', 0, 10, 'Integer')

# 目的函数
problem += 100 * x_1 + 550 * x_2 + 1200 * x_3 + 2500 * x_4 + 5200 * x_5 + 14500 * x_6

# 制約条件
problem += 120 * x_1 + 600 * x_2 + 1200 * x_3 + 2400 * x_4 + 4800 * x_5 + 11800 * x_6 <= amount_of_money

status = problem.solve()
print("Status", pulp.LpStatus[status])
print(x_1.value(), x_2.value(), x_3.value(), x_4.value(), x_5.value(), x_6.value())

結果であるが、予想通りの結果であった。

Status Optimal
2.0 0.0 1.0 0.0 0.0 0.0

貪欲戦略でよいのでは、という結論である。