<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Увидел у Игоря Викторовича в vk отличный пост
Step1:  X = [Titan, Naga, Djinn, Mage, Golem, Gargoyle, Gremlin, Sold gems]
Step2:  Решение найдено почти мгновенно.
Step3:  Последний элемент ответа 0 - камни продавать не нужно. Сила набранной армии
Step4:  Затраченные ресурсы
Step5:  Ртуть и камни потратили полностью, монеты еще остались.
Внимательный читатель мог заметить, что решение не совсем честное. Задачу я увидел уже глубокой ночью и воспользовался тем инструментом, что уже знал. Так повезло, что найденное решение оказалось целочисленным. Но вообще, это не всегда так. Вот результат для задачи с такими же условиями, но когда у Дениса только 100k золота
Step6:  Для общего случая ILP дальше не всегда можно просто докрутить до целых чисел. А это прекрасный повод забыть про родной L-BFGS и окунуться в мир целочисленных линейных задач.
Integer Linear Problem
Вообще, известно как с помощью дополняющих условий (Cutting-plane method) сводить задачу к целочисленной, но делать это на scipy не стоит.
Я начал копать с этой страницы
Step7:  Теперь пришлось продавать камни.
Step8:  Дальнобойные, воздушные
Step9:  Затраченные ресурсы
<ASSISTANT_TASK:>
Python Code:
import scipy.optimize
import numpy as np
import pandas as pd
gold = int(2 * 1e5)
gems = 115
mercury = 80
distant_min_health = 4000
air_min_health = 2000
gem_price = 500
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
Explanation: Увидел у Игоря Викторовича в vk отличный пост: https://vk.com/wall137669108_516
Problem
Simple solution in continuous space
End of explanation
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)]
%%time
result = scipy.optimize.linprog(loss_function, A, b, bounds=bounds)
Explanation: X = [Titan, Naga, Djinn, Mage, Golem, Gargoyle, Gremlin, Sold gems]
End of explanation
result
Explanation: Решение найдено почти мгновенно.
End of explanation
-np.dot(result.x, np.array(A[0])), -np.dot(result.x, A[1])
Explanation: Последний элемент ответа 0 - камни продавать не нужно. Сила набранной армии: 12875.
Сила существ дальнего боя / воздушной армии:
End of explanation
np.dot(result.x, A[2]), np.dot(result.x, A[3]), np.dot(result.x, A[4])
Explanation: Затраченные ресурсы:
End of explanation
result.x
Explanation: Ртуть и камни потратили полностью, монеты еще остались.
Внимательный читатель мог заметить, что решение не совсем честное. Задачу я увидел уже глубокой ночью и воспользовался тем инструментом, что уже знал. Так повезло, что найденное решение оказалось целочисленным. Но вообще, это не всегда так. Вот результат для задачи с такими же условиями, но когда у Дениса только 100k золота:
End of explanation
import pulp
problem = pulp.LpProblem("Heroes III", pulp.LpMaximize)
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]
# gain function
problem += np.dot(army, units.health.values)
# 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
%%time
pulp.LpStatus[problem.solve()]
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()]
Explanation: Для общего случая ILP дальше не всегда можно просто докрутить до целых чисел. А это прекрасный повод забыть про родной L-BFGS и окунуться в мир целочисленных линейных задач.
Integer Linear Problem
Вообще, известно как с помощью дополняющих условий (Cutting-plane method) сводить задачу к целочисленной, но делать это на scipy не стоит.
Я начал копать с этой страницы: http://prod.sandia.gov/techlib/access-control.cgi/2013/138847.pdf
И остановился сразу как только нашел слово GNU. Интересно, что основатель проекта из МАИ. Список python биндингов: https://en.wikibooks.org/wiki/GLPK/Python
End of explanation
optimal_army = [unit.value() for unit in army]
Explanation: Теперь пришлось продавать камни.
End of explanation
np.dot(optimal_army, units.health * units.distant), np.dot(optimal_army, units.health * units.air)
Explanation: Дальнобойные, воздушные
End of explanation
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]), \
Explanation: Затраченные ресурсы
End of explanation
<END_TASK>