多背包限制物品可以放入的背包数量

Question

如果我有一个多背包，但我想限制每件物品可以放置的背包数量，从示例中似乎不太清楚。所以，比如我有10个背包，我有可以同时放在两个背包里的物品。我有这样的代码：

x[(item, bag)] = model.NewIntVar(0, 1, 'x_%s_%s' % (item, bag))
model.Add(
    len(set(bag
        for item in data['all_items']
        for bag in data['all_bags']
        if x[(item, bag)] > 0
    )
) <= 2)

我该如何创建这样的条件？

Answer 1

您可以创建一个布尔值来指示物品是否在包中。

presence[(item, bag)] = model.NewBoolVar("")
model.Add(x[item, bag] > 0).OnlyEnforceIf(presence[item, bag])
model.Add(x[item, bag] == 0).OnlyEnforceIf(presence[item, bag].Not())

那你就可以约束这个和

for item in data["all_items"]:
    model.Add(sum(x[item, bag] for bag in data["all_bags"]) <= 2)

这里有一个例子：https://github.com/google/or-tools/blob/stable/examples/python/balance_group_sat.py#L102

编辑：刚刚意识到您的 x[(item, bag)] 实际上是布尔值。所以你可以忽略第一部分

多背包限制物品可以放入的背包数量

multi knapsack with limit on number of knapsacks an item can be placed in

or-tools