使用重复约束优化

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 pywraplpsolver = 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 = 100solver.Add(solver.Sum([x[i] for i in range(MAX_ITEMS)]) == total_chosen)max_cost = 5.0for 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 个最好的，然后重复该顺序。