Python 中物品总数限制的背包问题

Question

我正在尝试用 Python 解决一个有额外要求的背包问题。我找到了很多背包代码和数学解释，但我找不到任何适合我想要做的事情的东西。老实说，数学信息让我难以理解，所以这就是我在这里问的原因。我很乐意学习使用任何可用的库，只要它是免费的。 Numpy、pandas、ortools 等

假设我有 20 美元，我想购买 6 瓶混合搭配的六瓶装啤酒。每种啤酒都有名称、类型、价格（类似背包的“重量”）和评价分数（类似背包的“价值”）。
我想购买评论分数最高的组合，同时也遵循以下规则：

总花费少于 20 美元
刚好买 6 瓶啤酒
我还想确保我总是得到 2 瓶拉格啤酒、1 瓶世涛啤酒和 1 瓶琥珀啤酒。其他 2 瓶啤酒可以是任何啤酒，但所有 6 瓶啤酒都必须是独一无二的。

这只是一小部分数据的例子。我知道蛮力可能在这里工作，但我的真实数据要大得多，我第一次尝试（在发现这是一个常见问题之前）用蛮力从未完成，并且需要 way 太长找到解决办法。所以我正在寻找比蛮力更好的东西。

capacity = 6
money = 20

beers = [ 
  {"name":"Beer1",  "type":"Lager",   "price":3.50, "score":4.1},
  {"name":"Beer2",  "type":"Porter",  "price":4.90, "score":4.5},
  {"name":"Beer3",  "type":"IPA",     "price":3.70, "score":4.0},
  {"name":"Beer4",  "type":"Stout",   "price":3.20, "score":4.2},
  {"name":"Beer5",  "type":"Amber",   "price":3.80, "score":3.9},
  {"name":"Beer6",  "type":"Stout",   "price":2.70, "score":2.9},
  {"name":"Beer7",  "type":"IPA",     "price":2.50, "score":3.2},
  {"name":"Beer8",  "type":"Pilsner", "price":3.10, "score":4.0},
  {"name":"Beer9",  "type":"Amber",   "price":3.00, "score":4.1},
  {"name":"Beer10", "type":"Porter",  "price":2.80, "score":3.3},
  {"name":"Beer11", "type":"IPA",     "price":3.70, "score":4.0},
  {"name":"Beer12", "type":"Lager",   "price":3.20, "score":4.2},
  {"name":"Beer13", "type":"Amber",   "price":3.30, "score":3.5},
  {"name":"Beer14", "type":"Stout",   "price":2.90, "score":2.8},
  {"name":"Beer15", "type":"Lager",   "price":3.20, "score":4.2},
]

所需的输出将是为解决方案选择的名称列表，如下所示：["Beer12","Beer14","Beer13","Beer1","Beer7","Beer6"]

感谢观看。我希望我们能找到一个解决方案，为我和其他任何人在未来试图解决类似的问题。

Answer 1

它可以像下面的例子。

我们：

使用 cp-sat 作为求解器
规模价格和分数能够使用积分域
- cp-sat 需要这个

可能包含一个错误，因为我没有对其进行过多检查，但无论如何它更多的是关于一般概念。它还表明求解器的建模能力。

代码

from ortools.sat.python import cp_model

# DATA
capacity = 6
money = 20
beers = [ 
  {"name":"Beer1",  "type":"Lager",   "price":3.50, "score":4.1},
  {"name":"Beer2",  "type":"Porter",  "price":4.90, "score":4.5},
  {"name":"Beer3",  "type":"IPA",     "price":3.70, "score":4.0},
  {"name":"Beer4",  "type":"Stout",   "price":3.20, "score":4.2},
  {"name":"Beer5",  "type":"Amber",   "price":3.80, "score":3.9},
  {"name":"Beer6",  "type":"Stout",   "price":2.70, "score":2.9},
  {"name":"Beer7",  "type":"IPA",     "price":2.50, "score":3.2},
  {"name":"Beer8",  "type":"Pilsner", "price":3.10, "score":4.0},
  {"name":"Beer9",  "type":"Amber",   "price":3.00, "score":4.1},
  {"name":"Beer10", "type":"Porter",  "price":2.80, "score":3.3},
  {"name":"Beer11", "type":"IPA",     "price":3.70, "score":4.0},
  {"name":"Beer12", "type":"Lager",   "price":3.20, "score":4.2},
  {"name":"Beer13", "type":"Amber",   "price":3.30, "score":3.5},
  {"name":"Beer14", "type":"Stout",   "price":2.90, "score":2.8},
  {"name":"Beer15", "type":"Lager",   "price":3.20, "score":4.2},]

# PREPROCESSING
n_beers = len(set([entry['name'] for entry in beers]))

# MODEL
model = cp_model.CpModel()
x_select = [model.NewBoolVar('') for i in range(n_beers)]

# select exactly "capacity"
model.Add(sum(x_select) == capacity)

# spend not too much -> # ASSUMPTION: * 100 makes all the values integral
model.Add(sum([x_select[i] * int(round(beers[i]['price']*100)) for i in range(n_beers)]) <= money * 100)

# >= 2 lagers needed
model.Add(sum([x_select[i] for i in range(n_beers) if beers[i]['type'] == 'Lager']) >= 2)

# >= 1 Stout needed
model.Add(sum([x_select[i] for i in range(n_beers) if beers[i]['type'] == 'Stout']) >= 1)

# >= 1 Amber needed
model.Add(sum([x_select[i] for i in range(n_beers) if beers[i]['type'] == 'Amber']) >= 1)

# maximize sum of scores selected -> # ASSUMPTION: * 10 makes all the values integral
model.Maximize(sum([x_select[i] * int(round(beers[i]['score']*10)) for i in range(n_beers)]))

# SOLVE
solver = cp_model.CpSolver()
solver.parameters.log_search_progress = True
model.Proto().objective.scaling_factor = -1./10         # inverse scaling for solver logging output
status = solver.Solve(model)

if status == cp_model.OPTIMAL:
  selected = [i for i in range(n_beers) if solver.Value(x_select[i]) == 1]
  print("\n".join([str(beers[i]) for i in selected]))

修剪输出

status: OPTIMAL
objective: 24.8
best_bound: 24.8
booleans: 8
conflicts: 0
branches: 19
propagations: 20
integer_propagations: 42
restarts: 17
lp_iterations: 4
walltime: 0.0689822
usertime: 0.0689823
deterministic_time: 2.03413e-05
primal_integral: 1.69201e-05
Total cuts added: 3 (out of 4 calls) worker: ''
  - num simplifications: 0
  - added 1 cut of type 'CG'.
  - added 1 cut of type 'MIR_1'.
  - added 1 cut of type 'MIR_2'.
{'name': 'Beer1', 'type': 'Lager', 'price': 3.5, 'score': 4.1}
{'name': 'Beer4', 'type': 'Stout', 'price': 3.2, 'score': 4.2}
{'name': 'Beer8', 'type': 'Pilsner', 'price': 3.1, 'score': 4.0}
{'name': 'Beer9', 'type': 'Amber', 'price': 3.0, 'score': 4.1}
{'name': 'Beer12', 'type': 'Lager', 'price': 3.2, 'score': 4.2}
{'name': 'Beer15', 'type': 'Lager', 'price': 3.2, 'score': 4.2}

Python 中物品总数限制的背包问题

Knapsack problem with a total item limit in Python

python

mathematical-optimization

knapsack-problem

代码

修剪输出