背包与相互排斥的物品

Question

虽然标准背包问题可以通过动态规划来解决，但我试图稍微扭曲一下这个问题，以明确我的概念，但我发现它可能比我想象的更难。

最初的背包问题是，给定一个大小为W的背包，以及一个重量为W[i]且值为v[i]的物品列表，找出总价值最高的背包中适合的物品子集。

据我所知，这可以通过动态规划O（Wn）实现，其中n是项目数。

现在，如果我尝试添加m约束，它们中的每一个都是一对只能相互独占地拾取的项目（即，如果存在项目a和项目B的约束，那么我只能选择其中一个，但不能同时选择两个）

在这样的约束条件下，这个问题仍然可以通过O（Wn）中的动态规划来解决吗？

Answer 1

假设：每个元素都包含在atmost一个约束中。

对于通常的背包问题，问题表现出的最优子结构如下：

对于每个项目，可以有两种情况：
1。该项目包含在解决方案中
2。该项目未包含在解决方案中。

因此，n项的最佳解决方案由以下两个值的最大值给出
1。通过n-1项目和W重量获得的最大值
2v_n通过n-1项目和W-W_n重量获得的最大值。

现在，如果我们添加约束，即nth或（n-1）th项可以存在于解中，那么n项的最佳解由以下三个值的最大值给出
1。通过n-2项目和W重量获得的最大值
2v_n通过n-2项目和W-W_n重量获得的最大值
3<代码>v_Un（n-1）通过n-2项目和W-W_Un（n-1）重量获得的最大值。

因此，我们将约束中的每一对元素视为单个元素，并在O（Wn）time中执行动态规划算法。