0

我有一组许多（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，第一个和第三个项目是蓝色的（等等）。

我无法使用谷歌或工具来制定这个。

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 个项目，这些项目在成本限制的情况下最大化利润，但我坚持如何将其扩展到选择项目以保证第一个是蓝色等。

在制定约束和目标方面的任何帮助都会非常有帮助。谢谢！

4

1 回答 1

2

与其用 BoolVar 表示选择的项目，不如考虑制作一个包含 20 个 IntVar 且域为 0..MAX_ITEMS 的列表。从那里做这样的事情应该相当容易：

solver.Add(chosens[0].IndexOf(all_items)[3] == 1)
solver.Add(chosens[2].IndexOf(all_items)[3] == 1)

selecteds[i].IndexOf(all_items) 仅表示 all_items[IndexOfChosen], IE：为第 I 个位置选择的任何项目。如果您采用这种方法，请不要忘记 MakeAllDifferent！

于 2018-11-19T08:34:41.473 回答