01背包专门化

Question

经典背包。

这里有一个转折：在这些物品中，我需要确保我有从不同类别中提取的特定数量（不是最高的，而是确切的数量）。

所以让我们假设我们有类别

null

Answer 1

一种可能的ILP/LP配方（最明显的一种，但从来没有一种配方）可能是：（未经测试）

maximize sum(v[i] * x[i])
subject to:
0 <= x[i] <= 1        // can take every item at most once
sum(w[i] * x[i]) <= W // don't go over the weight limit
F <= sum(f[i] * x[i]) <= F + 1 // take F or F+1 food items
T <= sum(t[i] * x[i]) <= T + 1 // take T or T+1 toys
C <= sum(c[i] * x[i]) <= C + 1 // take C or C+1 clothes
sum(x[i]) == F + T + C + M     // take exactly the right number of items

其中v[i]是值，w[i]是权重，f[i]是项目的“食物度”，t[i]是“丰满度”，现在您已经知道c[i]将是什么了。属于一个以上类别的物品会被计算为双倍或三倍（例如，如果你拿了一个可食用的玩具，它会被计算在玩具和食物中），这可以通过放入该物品的多个副本来避免，每个类别一个副本，每个副本只在一个类别中。

但现在真正的问题，如何才能解决呢？这仍然是一个积极研究的领域，但这里有一个想法在这种情况下应该很有效。