combinatorics - 带有要考虑约束的物品的背包

Question

我有 I1、I2、I3、I4 项，权重为 W1...W4，值 V1...V4。我想用最小的权重最大化值。这是一个传统的背包。然而，有些项目不能放在一起有一个小的限制。因此，可以说 I2 和 I3 不能一起使用。任何人都可以提供动态编程解决方案或任何其他解决方案。

Answer 1

有了这个约束，问题就变得非常强（与离散背包相反，它只是弱 NP-hard）NP-hard。假设所有物品的重量为 1，价值为 1。

决定你是否能达到k值（假设背包容量 >= k）相当于找到k个它们之间没有约束的物品。这是一个已知的 NP-hard 问题：独立集。

如果您对约束的性质有一些额外的了解，这可能会更容易。