У меня есть набор из многих (более 10000) предметов, из которых я должен выбрать ровно 20 предметов. Я могу выбрать каждый товар только один раз. Мои вещи имеют прибыль и затраты, а также несколько логических свойств (таких как цвет). Мне нужно вывести результаты в определенном порядке: в частности, мне нужно, чтобы первый и третий элементы были синего цвета, а второй и четвертый элементы - красным.
Каждый элемент представлен в виде кортежа:
item = ('item name', cost, profit, is_blue, is_red)
в качестве примера
vase = ['Ming Vase', 1000, 10000, 0, 1]
plate = ['China Plate', 10, 5, 1, 0]
, а общий набор предметов представляет собой список списков:
items = [item1, item2, ..., itemN].
Мои доходы и расходы также перечислены:
profits = [x[2] for x in items]
costs = [x[1] for x in items]
Для каждого выбранного элемента должно быть минимальное значение, а минимум 5 элементов должен иметь свойство (is_blue), установленное в 1.
Я хочу выбрать 20 самых дешевых предметов с наибольшим значением, так что у 5 из них флаг is_blue установлен в 1, а первый и третий элементы имеют синий цвет (и т. Д.).
У меня проблемы с формулировкой с помощью инструментов Google OR.
from ortools.linear_solver import pywraplp
solver = pywraplp.Solver('SolveAssignmentProblemMIP',
pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
x = {}
for i in range(MAX_ITEMS):
x[i] = solver.BoolVar('x[%s]' % (i))
#Define the constraints
total_chosen = 20
solver.Add(solver.Sum([x[i] for i in range(MAX_ITEMS)]) == total_chosen)
blues = [x[3] for x in items]
solver.Add(solver.Sum([blues[i] * x[i] for i in .
диапазон (MAX_ITEMS)])> = 5)
max_cost = 5.0
for i in range(MAX_ITEMS):
solver.Add(x[i] * cost[i] <= max_cost)
solver.Maximize(solver.Sum([profits[i] * x[i] for i in range(total_chosen)]))
sol = solver.Solve()
Я могу получить набор предметов, которые я выбрал:
for i in range(MAX_ITEMS):
if x[i].solution_value() > 0:
print(item[i].item_name)
Это прекрасно работает - он выбирает набор из 20 предметов, которые максимизируют прибыль в зависимости от ограничения затрат, но я застрял на том, как расширить это до выбора предметов таким образом, чтобы гарантировать, что первый синий и т. Д.
Любая помощь в формулировании ограничений и целей была бы действительно полезной. Спасибо!