使用重复约束优化

Question

我有很多（10000+）个项目，我必须从中选择k项目。我只能根据订购限制多次选择每个项目：如果我在位置 1 中选择了一个项目，则在位置 21 之前我无法选择它。我的项目有利润和成本。

每个项目都表示为一个元组：

item = ('item name', cost, profit)

举个例子

vase = ['Ming Vase', 1000, 10000]

plate = ['China Plate', 10, 5]

项目的总集是一个列表列表：

items = [item1, item2, ..., itemN].

我的利润和成本也列出来了：

profits = [x[2] for x in items]

costs = [x[1] for x in items]

对于选择的每个项目，它需要有一个最小值，并且该项目不能在接下来的 19 个项目中重复使用。我想根据此限制选择价值最高的 k 个最便宜的物品，但我很难制定它。

我在使用 google OR 工具制定这个时遇到了麻烦。以下只是获得最好的k（在这种情况下为 100），没有任何额外的限制

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 = 100

solver.Add(solver.Sum([x[i] for i in range(MAX_ITEMS)]) == total_chosen)

max_cost = 5.0

for i in range(num_recipes):

    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)

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

Answer 1

一个想法，如果您为前 20 个对象创建最佳解决方案，您是否可以重复该模式直到序列结束？如果是，请按价值对您的项目进行排序，即 20 个最好的，然后重复该顺序。