Увидел у Игоря Викторовича в vk отличный пост: https://vk.com/wall137669108_516
In [1]:
import scipy.optimize
import numpy as np
import pandas as pd
In [2]:
gold = int(2 * 1e5)
gems = 115
mercury = 80
distant_min_health = 4000
air_min_health = 2000
gem_price = 500
In [3]:
units = [
{'name': 'titan', 'health': 300, 'gold': 5000, 'mercury': 1, 'gems': 3, 'available': 10},
{'name': 'naga', 'health': 120, 'gold': 1500, 'mercury': 0, 'gems': 2, 'available': 20},
{'name': 'djinn', 'health': 60, 'gold': 750, 'mercury': 1, 'gems': 1, 'available': 30},
{'name': 'mage', 'health': 40, 'gold': 500, 'mercury': 1, 'gems': 1, 'available': 55},
{'name': 'golem', 'health': 35, 'gold': 400, 'mercury': 1, 'gems': 0, 'available': 60},
{'name': 'gargoyle', 'health': 20, 'gold': 200, 'mercury': 0, 'gems': 0, 'available': 110},
{'name': 'gremlin', 'health': 4, 'gold': 70, 'mercury': 0, 'gems': 0, 'available': 500},
]
distant = ['titan', 'mage', 'gremlin']
air = ['djinn', 'gargoyle']
units = pd.DataFrame(units)
units.index = units.name
units['distant'] = 0
units['air'] = 0
units.loc[distant, 'distant'] = 1
units.loc[air, 'air'] = 1
units
Out[3]:
X = [Titan, Naga, Djinn, Mage, Golem, Gargoyle, Gremlin, Sold gems]
In [4]:
loss_function = -np.hstack([units.health, [0]])
A = [(-units.health * units.distant).tolist() + [0],
(-units.health * units.air).tolist() + [0],
units.mercury.tolist() + [0],
units.gems.tolist() + [1],
units.gold.tolist() + [-gem_price]]
b = [-distant_min_health, -air_min_health, mercury, gems, gold]
bounds = [(0, available) for available in units.available] + [(0, gems)]
In [5]:
%%time
result = scipy.optimize.linprog(loss_function, A, b, bounds=bounds)
Решение найдено почти мгновенно.
In [6]:
result
Out[6]:
Последний элемент ответа 0 - камни продавать не нужно. Сила набранной армии: 12875.
Сила существ дальнего боя / воздушной армии:
In [7]:
-np.dot(result.x, np.array(A[0])), -np.dot(result.x, A[1])
Out[7]:
Затраченные ресурсы:
In [8]:
np.dot(result.x, A[2]), np.dot(result.x, A[3]), np.dot(result.x, A[4])
Out[8]:
Ртуть и камни потратили полностью, монеты еще остались.
Внимательный читатель мог заметить, что решение не совсем честное. Задачу я увидел уже глубокой ночью и воспользовался тем инструментом, что уже знал. Так повезло, что найденное решение оказалось целочисленным. Но вообще, это не всегда так. Вот результат для задачи с такими же условиями, но когда у Дениса только 100k золота:
In [10]:
result.x
Out[10]:
Для общего случая ILP дальше не всегда можно просто докрутить до целых чисел. А это прекрасный повод забыть про родной L-BFGS и окунуться в мир целочисленных линейных задач.
Вообще, известно как с помощью дополняющих условий (Cutting-plane method) сводить задачу к целочисленной, но делать это на scipy не стоит.
Я начал копать с этой страницы: http://prod.sandia.gov/techlib/access-control.cgi/2013/138847.pdf И остановился сразу как только нашел слово GNU. Интересно, что основатель проекта из МАИ. Список python биндингов: https://en.wikibooks.org/wiki/GLPK/Python
In [11]:
import pulp
In [12]:
problem = pulp.LpProblem("Heroes III", pulp.LpMaximize)
In [13]:
titan = pulp.LpVariable('titan', lowBound=0, upBound=units.loc['titan'].available, cat='Integer')
naga = pulp.LpVariable('naga', lowBound=0, upBound=units.loc['naga'].available, cat='Integer')
djinn = pulp.LpVariable('djinn', lowBound=0, upBound=units.loc['djinn'].available, cat='Integer')
mage = pulp.LpVariable('mage', lowBound=0, upBound=units.loc['mage'].available, cat='Integer')
golem = pulp.LpVariable('golem', lowBound=0, upBound=units.loc['golem'].available, cat='Integer')
gargoyle = pulp.LpVariable('gargoyle', lowBound=0, upBound=units.loc['gargoyle'].available, cat='Integer')
gremlin = pulp.LpVariable('gremlin', lowBound=0, upBound=units.loc['gremlin'].available, cat='Integer')
sold_gems = pulp.LpVariable('sold gems', lowBound=0, upBound=gems, cat='Integer')
army = [titan, naga, djinn, mage, golem, gargoyle, gremlin]
In [14]:
# gain function
problem += np.dot(army, units.health.values)
In [15]:
# restrictions
problem += np.dot(army, units.health * units.distant) >= distant_min_health
problem += np.dot(army, units.health * units.air) >= air_min_health
problem += np.dot(army, units.mercury) <= mercury
problem += np.dot(army + [sold_gems], units.gems.tolist() + [1]) <= gems
problem += np.dot(army + [sold_gems], units.gold.tolist() + [-gem_price]) <= gold
In [16]:
%%time
pulp.LpStatus[problem.solve()]
Out[16]:
In [17]:
solution = pd.DataFrame([{'value': parameter.value()} for parameter in problem.variables()],
index=[parameter.name
for parameter in problem.variables()])
solution.loc[['sold_gems'] + units.name.tolist()]
Out[17]:
Теперь пришлось продавать камни.
In [18]:
optimal_army = [unit.value() for unit in army]
Дальнобойные, воздушные
In [19]:
np.dot(optimal_army, units.health * units.distant), np.dot(optimal_army, units.health * units.air)
Out[19]:
Затраченные ресурсы
In [20]:
np.dot(optimal_army, units.mercury), \
np.dot(optimal_army + [sold_gems.value()], units.gems.tolist() + [1]), \
np.dot(optimal_army + [sold_gems.value()], units.gold.tolist() + [-gem_price]), \
Out[20]: