具有依赖项权重的0/1背包问题？

Question

标准的 0/1 背包问题要求每个物品的重量都不依赖于其他物品，因此动态规划是解决该问题的一种有效算法。但现在我遇到了一个类似但是扩展了的问题：

新物品的重量取决于已经放入背包中的先前物品。

例如，我们有五个物品 a, b, c, d 和 e，它们的重量分别为 w_a, ..., w_e。其中物品 b 和 c 存在重量依赖性。

当将物品 b 放入背包中时，物品 c 的重量将比 w_c 小，因为它可以与 b 共享一些空间，即 weight(b&c) < w_b + w_c。同样地，当将物品 c 放入背包中时，物品 b 的重量将比 w_b 小。

这种不确定性导致原始 DP 算法失败，因为它依赖于以前迭代的正确性，而这种正确性现在可能不正确了。我阅读了一些关于背包问题的论文，但它们要么有依赖于利润的依赖性（二次背包问题），要么具有遵循随机分布的可变重量（随机背包问题）。我也注意到了之前的一个问题：带加权边的 1/0 背包变体，但只有一个非常通用的答案可用，并且没有关于这个背包问题的名称的答案。

现有的解决方案：

我还读过一篇关于DBMS优化的论文，其中他们将相关项作为一个组合项进行背包问题求解。如果将这种技术应用到我们的例子中，那么背包中的项将是a、bc、d、e，因此这四个项之间就没有依赖关系了。然而，很容易构造一个不会得到最优结果的例子，比如当“具有较小重量和效益”的物品与“具有较大重量和效益”的物品分组时。在这个例子中，“小”物品不应该被选择，但却与“大”物品一起被选择。

问题：

是否有任何有效的求解技巧可以得到最优解，或者至少有一些误差保证？或者我对模型化这个问题的方向是错误的吗？

- Paddy Xu

---

看起来你的问题受到了一些负评。我不太赞同给出负评，但这可能是因为你问是否有关于这个问题的研究，这可能被解释为请求“站外资源”，而这是不符合主题的。 - samgak

@samgak 感谢您的评论。我已经修改了我的问题，更加专注于可能的解决方案。 - Paddy Xu

这个问题正在Meta上讨论。 - johnnyRose

对于背包问题，您可以尝试标准的B&B方法，只需根据在计算上下界时哪些物品已经放入了背包来更新物品的重量（这应该不难）。 - Holt

@PaddyXu 写下你自己的答案并解释一下上/下界计算，然后将其标记为已接受的答案，这将是一个更好的答案，而不是简单地说“尝试使用自定义 B&B。” ;) - Holt

Answer 1

你能不能不要有物品a、b、c、bc、d和e？可能需要限制b和bc不能同时在背包中，同样的，c和bc也不能同时在背包中。我的理解是这将是一个正确的解决方案，因为任何具有b和c的解决方案都可以通过用bc替换两者来改进（根据定义）。成员资格的限制应该处理任何其他情况。

- Jakub Hampl

---

如果所有物品之间存在依赖关系，那么一旦物品数量开始增加，这种方法就会变得相当低效且难以处理。例如，对于物品a、b、c、d、e，你需要创建ab、ac、ad、ae、bc、bd、be、cd、ce和de，但还要创建abc（因为如果把a、b和c放入背包中怎么办？）以及所有三元组、四元组等等。基本上，你要为所有可能的解决方案创建一个项。 - Holt

@Holt 或许，但其中很多可以轻易被主导，所以你可以相对便宜地将它们从最初的考虑中去除。 - Jakub Hampl

感谢您的回答。然而，当算法（例如DP）同时选择'b'和'bc'时，这个想法可能无法正常工作。在这种情况下，因为选择'bc'等同于选择'b'，并且'b'的权重将变为'0'，依赖关系仍然存在。 - Paddy Xu

Answer 2

这是一个非常有趣的问题，我已经研究了一段时间。首先要考虑的是具有相关项重量/价值的二进制背包问题根本不是简单的。您可以考虑使用贝叶斯网络、马尔可夫模型和其他类似的技术来解决这个问题。然而，任何实际方法都必须对优化模型或其输入做出一些假设。以下是一个将具有价值依赖项的二进制背包问题形式化的示例。https://arxiv.org/pdf/1702.06662.pdf 在这项工作中，作者提出使用模糊图来建模输入（与价值相关的依赖关系），然后使用所提出的整数线性规划模型来解决优化问题。该工作的扩展版本已被接受发表，并将很快在线上提供。

如果需要进一步信息，请随时联系我。如果需要，我还可以为您提供模型的源代码。

- Davoud Mougouei

---

我希望如果仍然可用，能够提供解决此问题的代码。 - Gulzar

Answer 3

最终，我通过@Holt提出的B&B方法解决了问题。以下是关键设置：

(0) 在运行B&B算法之前，根据它们的依赖性将所有项目分组。同一分区中的所有项目都与该组中的所有其他项目具有权重依赖性，但与其他组中的项目没有依赖关系。

B&B的设置：

(1) 上限：假设当前项目具有最小重量，即假设所有依赖项都存在。

(2) 下限：假设当前项目具有最大重量，即假设所有依赖项不存在。

(3) 当前重量：计算实际当前重量。

通过玩弄我们在步骤0中获得的组，可以在线性时间内完成上述所有计算。具体来说，在获取这些权重时，仅扫描当前组中的项目（当前项目所在的组）就足够了-其他组中的项目与当前项目没有依赖关系，因此不会改变当前项目的实际重量。

- Paddy Xu