背包问题中的互斥项

Question

背包问题中的互斥项

algorithmdynamic-programming

8

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

原始的背包问题是这样的：给定一个大小为W的背包和一个物品列表，其中物品的重量为w[i]，价值为v[i]，找到能够放入背包中且总价值最高的物品子集。

据我所知，这可以通过动态规划以O(Wn)的时间复杂度完成，其中n是物品数量。

现在，如果我尝试添加m个限制条件，每个条件都是一对互斥选择的物品（即如果存在物品A和物品B的限制，则我只能选择其中一个而不能同时选择两个）

在这样的限制条件下，这个问题仍然可以在O(Wn)的时间复杂度内通过动态规划解决吗？

- shole

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Abhishek Bansal · Accepted Answer

假设：每个元素最多只包含在一个约束条件中。

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

对于每个物品，有两种情况： 1. 物品包含在解决方案中 2. 物品不包括在解决方案中。

因此，n个物品的最优解为以下两个值的最大值。 1. 通过n-1个物品和W重量获得的最大价值。 2. v_n + 通过n-1个物品和W-w_n重量获得的最大价值。

现在，如果我们添加一个约束条件，即第n个或(n-1)个项目可以存在于解决方案中，则n个项目的最优解为以下三个值的最大值。 1. 通过n-2个物品和W重量获得的最大价值。 2. v_n + 通过n-2个物品和W-w_n重量获得的最大价值。 3. v_(n-1) + 通过n-2个物品和W-w_(n-1)重量获得的最大价值。

因此，我们将约束条件中的每一对元素视为单个元素，并以O(Wn)时间执行动态规划算法。