标准的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 …