Pad*_* Xu 29 algorithm knapsack-problem
标准的0/1背包要求每件物品的重量独立于其他物品.然后DP是解决方案的有效算法.但是现在我遇到了类似但是这个问题的扩展,那个
新物品的重量取决于背包中已有的物品.
例如,我们有5个项目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优化的论文中阅读了一个近似的解决方案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".在此示例中,不应在解决方案中选择"小"项,而是与"大"项一起选择.
题:
是否有任何有效的解决方法可以获得最佳结果,或者至少有一些错误保证？或者我是否采取了错误的方向来解决这个问题？
难道你没有项目a,b,c,bc,d和e？可能带有约束b和bc不能在背包和同样如此具有既c和bc？我的理解是,这将是一个正确的解决方案,因为任何解决方案已经b并且c可以通过替换bc(通过定义)来改进.对会员资格的限制应该照顾任何其他情况.
最后我用@Holt提出的B&B方法解决了这个问题。下面是关键设置：
(0) 在运行 B&B 算法之前，根据依赖项对所有项进行分组。一个分区中的所有项目与同一组中的所有其他项目具有权重依赖性，但与其他组中的项目不具有权重依赖性。
民宿设置：
(1)上界：假设当前项具有最小权重，即假设所有依赖关系都存在。
(2)下界：假设当前项具有最大权重，即假设所有依赖关系不存在。
(3)当前重量：计算当前实际重量。
通过使用我们在步骤 0 中获得的组，可以在线性时间内完成所有上述计算。具体来说，在获取这些权重时，仅扫描当前组中的项目（当前项目所在的组）就足够了 - items其他组与当前组没有依赖关系，因此不会改变当前项的实际权重。