一尘不染

0/1背包的重量取决于物品?

algorithm

标准的0/1背包要求每个物品的重量都与其他物品无关。那么,DP是解决该问题的有效算法。但是现在我遇到了类似但又扩展了这个问题,

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

例如 ,我们有5个项目abcde体重w_a,… w_e。项目,bc具有重量依赖性。

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。如果使用这种技术进入我们的例子中,在背包的物品会abcde,因此有这四个项目中的任何两者之间没有更多的依赖关系。但是,构造一个无法获得最佳结果的示例很容易,例如when
an item with "small weight and benefit" is grouped with another item with "large weight and benefit"。在此示例中,不应在解决方案中选择“小”项目,而应与“大”项目一起选择。

题:

是否有任何一种有效的求解技术可以获得最佳结果,或者至少可以保证某些错误?还是我为这个问题建模的方向错误?


阅读 269

收藏
2020-07-28

共1个答案

一尘不染

最后,我设法用@Holt提出的B&B方法解决了这个问题。这是关键设置:

(0)在运行B&B算法之前,对所有项目进行分组取决于其依赖性。一个分区中的所有项目都与同一组中的所有其他项目具有权重相关性,而与其他组中的项目则不具有权重相关性。

B&B的设置:

(1)上限:假设当前项的权重 最小 ,即假设所有依赖项都存在。

(2)下限:假设当前项目具有 最大 权重,即假设所有依赖项都不存在。

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

通过与在步骤0中获得的组进行比较,可以在线性时间内完成所有上述计算。具体地说,当获得这些权重时,仅扫描当前组(当前项目所在的组)中的项目就足够了-
项目在其他组中,与当前组没有依赖性,因此不会更改当前项目的实际权重。

2020-07-28