0/1背包的重量取决于物品? [英] 0/1 knapsack with dependent item weight?

问题描述

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

The standard 0/1 knapsack requires that the weight of every item is independent to others. Then DP is a efficient algorithm towards the solution. But now I met a similar but extensions of this problem, that

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

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具有重量依赖性.

For example, we have 5 items a, b, c, d and e with weight w_a, ..., w_e. item b and c have weight dependency.

当背包中已经装有b时，c的重量将比w_c小 ，因为它可以与b共享空间，即weight(b&c) < w_b + w_c.对称地，当背包中已经装有c时，b的重量将小于w_b.

When b is already in the knapsack, the weight of item c will be smaller than w_c because it can share some space with b, i.e. weight(b&c) < w_b + w_c. Symmetrically, when c is already in the knapsack, the weight of b will be smaller than w_b.

这种不确定性会导致原始DP算法失败，因为它取决于先前迭代的正确性，而现在可能无法纠正.我已经阅读了一些有关背包的论文，但是它们要么具有依赖于 profit (二次背包问题)的依赖关系，要么具有随随机分布而变化的权重(随机背包问题).我也知道上一个问题 1/0带有加权边缘的背包变化，但是只有一个非常通用的答案，而没有关于这个背包的名字的答案.

This uncertainty results a failure of original DP algorithm, since it depend on the correctness of previous iterations which may not correct now. I have read some papers about knapsack but they either have dependencies subjected to profit (quadratic knapsack problem), or have variable weight which follows a random distribution (stochastic knapsack problem). I have also aware of the previous question 1/0 Knapsack Variation with Weighted Edges, but there is only a very generic answer available, and no answer about what is the name of this knapsack.

一个现有的解决方案:

我还阅读了一篇论文中的一种近似解决方案有关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"时.在此示例中，不应在解决方案中选择小"项目，而应与大"项目一起选择.

I have also read one approximate solution in a paper about DBMS optimizations, where they group the related items as one combined item for knapsack. If use this technique into our example, the items for knapsack will be a, bc, d, e, therefore there is no more dependencies between any two of these four items. However it is easy to construct an example that does not get optimal result, like when an item with "small weight and benefit" is grouped with another item with "large weight and benefit". In this example, the "small" item should not be selected in solution, but is selected together with the "large" item.

问题:

是否有任何一种有效的求解技术可以获得最佳结果，或者至少具有一定的错误保证?还是我对这个问题进行建模时走错了方向?

Is there any kind of efficient solving techniques that can get optimal result, or at least with some error guarantee? Or am I taking the wrong direction for modelling this problem?

推荐答案

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

In the end I managed to solve the problem with the B&B method proposed by @Holt. Here is the key settings:

(0)在运行B& B算法之前，将所有项目依赖于它们的依赖性进行分组.一个分区中的所有项目与同一组中的所有其他项目都具有重量依赖性，而其他组中的项目则不具有重量依赖性.

(0) Before running the B&B algorithm, group all items depend on their dependency. All items in one partition have weight dependency with all other items in the same group, but not with items in other groups.

B& B的设置:

Settings for B&B:

(1)上限:假定当前项目的权重为最小，即假设所有依赖项都存在.

(1) Upper-bound: assume that the current item has the minimum weight, i.e. assume all dependencies exist.

(2)下限:假定当前项目的权重为 maximum ，即假定所有依赖项都不存在.

(2) Lower-bound: assume that the current item has the maximum weight, i.e. assume all dependencies do not exist.

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

(3) Current weight: Calculate the real current weight.

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

All the above calculations can be done in a linear time by playing around with the groups we get in step 0. Specifically, when obtaining those weights, scanning only items in current group (the group which the current item be in) is enough - items in other groups have no dependencies with the current one, so it will not change the real weight of current item.

这篇关于0/1背包的重量取决于物品?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！