0/1 背包与相关项目重量？
0/1 knapsack with dependent item weight?
标准0/1背包要求每件物品的重量独立于其他物品。那么DP是一种高效的求解算法。但是现在我遇到了这个问题的类似但扩展，即
the weight of new items are dependent on previous items already in
the knapsack.
例如，我们有5个项目a、b、c、d和e 权重 w_a, ..., w_e。项目 b 和 c 具有权重依赖性。
当b已经在背包里时，物品c的重量会比w_c小，因为它可以分担一些space 与 b，即 weight(b&c) < w_b + w_c。对称地，当c已经在背包中时，b的重量会小于w_b。
这种不确定性导致原始 DP 算法失败，因为它取决于以前迭代的正确性，而现在可能无法纠正。我读过一些关于背包的论文，但它们要么具有依赖于 profit（二次背包问题），要么具有遵循随机分布的可变权重（随机背包问题）。之前的问题我也知道了，但是只有很笼统的回答，没有回答这个背包叫什么名字
一个现有的解决方案：
我还在 a paper 中阅读了一个关于 DBMS 优化的近似解决方案，其中 group the related items as one combined item for knapsack。如果在我们的示例中使用此技术，背包的项目将是 a、bc、d、e，因此这四个中的任何两个之间不再存在依赖关系项目。然而，很容易构造一个没有得到最佳结果的例子，比如 an item with "small weight and benefit" is grouped with another item with "large weight and benefit"。在这个例子中，"small"项不应该在解决方案中被选中，而是与"large"项一起被选中。
问题：
是否有任何一种高效的求解技术可以获得最佳结果，或者至少有一定的错误保证？还是我为这个问题建模的方向错误？
你不能有 a、b、c、bc、d 和 e 项吗？可能有一个限制，即 b 和 bc 不能同时在背包中，类似地，c 和 bc？我的理解是，这将是一个正确的解决方案，因为任何具有 b 和 c 的解决方案都可以通过用 bc（根据定义）替换两者来改进。对成员资格的限制应考虑到任何其他情况。
这是一个非常有趣的问题，我已经研究了一段时间。首先要考虑的是，具有相关项 weights/value 的二元背包问题一点也不简单。您可以考虑使用贝叶斯网络、马尔可夫模型和其他类似技术来解决这个问题。尽管如此，解决这个问题的任何实际方法都必须对优化模型或其输入做出一些假设。下面是用依赖于值的项目制定二元背包问题的示例。 https://arxiv.org/pdf/1702.06662.pdf
在这项工作中，作者建议使用模糊图对输入（与值相关的依赖项）进行建模，然后使用建议的整数线性规划模型来解决优化问题。该作品的扩展版本已被接受出版，并将很快在线提供。
如果您需要更多信息，请随时与我联系。如果需要，我还可以为您提供模型的源代码。
最后我用@Holt提出的B&B方式解决了问题。这是关键设置：
(0) 在运行 B&B 算法之前，根据依赖项对所有项目进行分组。一个分区中的所有项目都与同一组中的所有其他项目具有权重相关性，但与其他组中的项目无关。
民宿设置：
(1) 上限：假设当前项具有最小权重，即假设所有依赖项都存在。
(2) 下界：假设当前项具有最大权重，即假设所有依赖项都不存在。
(3)当前体重：计算真实的当前体重。
上述所有计算都可以通过在步骤 0 中获得的组进行操作，在线性时间内完成。具体来说，当获得这些权重时，仅扫描当前组中的项目（当前项目所在的组） ) 就足够了 - 其他组中的项目与当前项目没有依赖关系，因此不会改变当前项目的实际重量。
标准0/1背包要求每件物品的重量独立于其他物品。那么DP是一种高效的求解算法。但是现在我遇到了这个问题的类似但扩展，即
the weight of new items are dependent on previous items already in the knapsack.
例如，我们有5个项目a、b、c、d和e 权重 w_a, ..., w_e。项目 b 和 c 具有权重依赖性。
当b已经在背包里时，物品c的重量会比w_c小，因为它可以分担一些space 与 b，即 weight(b&c) < w_b + w_c。对称地，当c已经在背包中时，b的重量会小于w_b。
这种不确定性导致原始 DP 算法失败，因为它取决于以前迭代的正确性，而现在可能无法纠正。我读过一些关于背包的论文，但它们要么具有依赖于 profit（二次背包问题），要么具有遵循随机分布的可变权重（随机背包问题）。之前的问题我也知道了
一个现有的解决方案：
我还在 a paper 中阅读了一个关于 DBMS 优化的近似解决方案，其中 group the related items as one combined item for knapsack。如果在我们的示例中使用此技术，背包的项目将是 a、bc、d、e，因此这四个中的任何两个之间不再存在依赖关系项目。然而，很容易构造一个没有得到最佳结果的例子，比如 an item with "small weight and benefit" is grouped with another item with "large weight and benefit"。在这个例子中，"small"项不应该在解决方案中被选中，而是与"large"项一起被选中。
问题：
是否有任何一种高效的求解技术可以获得最佳结果，或者至少有一定的错误保证？还是我为这个问题建模的方向错误？
你不能有 a、b、c、bc、d 和 e 项吗？可能有一个限制，即 b 和 bc 不能同时在背包中，类似地，c 和 bc？我的理解是，这将是一个正确的解决方案，因为任何具有 b 和 c 的解决方案都可以通过用 bc（根据定义）替换两者来改进。对成员资格的限制应考虑到任何其他情况。
这是一个非常有趣的问题，我已经研究了一段时间。首先要考虑的是，具有相关项 weights/value 的二元背包问题一点也不简单。您可以考虑使用贝叶斯网络、马尔可夫模型和其他类似技术来解决这个问题。尽管如此，解决这个问题的任何实际方法都必须对优化模型或其输入做出一些假设。下面是用依赖于值的项目制定二元背包问题的示例。 https://arxiv.org/pdf/1702.06662.pdf
在这项工作中，作者建议使用模糊图对输入（与值相关的依赖项）进行建模，然后使用建议的整数线性规划模型来解决优化问题。该作品的扩展版本已被接受出版，并将很快在线提供。
如果您需要更多信息，请随时与我联系。如果需要，我还可以为您提供模型的源代码。
最后我用@Holt提出的B&B方式解决了问题。这是关键设置：
(0) 在运行 B&B 算法之前，根据依赖项对所有项目进行分组。一个分区中的所有项目都与同一组中的所有其他项目具有权重相关性，但与其他组中的项目无关。
民宿设置：
(1) 上限：假设当前项具有最小权重，即假设所有依赖项都存在。
(2) 下界：假设当前项具有最大权重，即假设所有依赖项都不存在。
(3)当前体重：计算真实的当前体重。
上述所有计算都可以通过在步骤 0 中获得的组进行操作，在线性时间内完成。具体来说，当获得这些权重时，仅扫描当前组中的项目（当前项目所在的组） ) 就足够了 - 其他组中的项目与当前项目没有依赖关系，因此不会改变当前项目的实际重量。