带有约束的背包问题

Question

我熟悉0/1背包问题。 但如果强加了以下约束......我如何解决问题？

1. 如果您选择某些项目'U'，您将无法选择其他项目'v'。

例如 物品作为[姓名，重量，价值]给出 物品是：
一个10 20
B 50 80
C 20 30
D 30 70
e 50 50

如果你选择b那么你就不能选择A.
如果您选择e，那么您无法选择C.
如果你选择D，那么你就不能选择A.
以类似的方式给出约束。


请给我一些方法来解决上述问题。任何帮助都受到高度赞赏。

Answer 1

标准动态编程方法可能不会为此问题工作，因为额外的“这一点或那个但不是两个”的约束来破坏重叠子问题属性。所以让我们打破大锤。

您可以轻松地将其作为 0-1整数线性编程问题并使用废弃求解器。对于给定示例（以及一些最大重量限制 $ w $ ），合适的0-1 ILP问题是：

最大化 $ 20a + 80b + 30c + 70d + 50e $
受到
$ a，b，c，d，e \ in \ {0，1 \} $
$ 10a + 50b + 20c + 30d + 50e \ Le W $
$ a + b \ le 1 $
$ c + e \ le 1 $
$ a + d \ le 1 $

虽然，对我来说，整数线性编程求解器是不明显的，这将充分利用问题的结构。因此，也许更专业的解决方案可能在实践中表现更好。