双背包算法

Question

3

假设你有一个装有易碎货物（例如蔬菜或水果）的仓库，每个容器只能取出一次。如果移动两次，它们会很快腐烂，无法再出售。

因此，如果给每个蔬菜容器赋值（取决于它们还能保持新鲜的时间），您希望先销售最低价值的容器。当客户要求一定重量时，您希望提供良好的服务，并提供精确的重量（因此需要从仓库中多取一些，在销售后扔掉多余部分）。

我不知道这个问题是否有名称，但我认为这是背包问题的对偶形式。在背包问题中，您希望最大化价值并将重量限制到最大值。而在这里，您希望最小化价值并将重量限制为最小值。

通过将仓库视为背包，并将其优化为最大价值和将重量限制为当前重量减去客户要求的重量的最大值，您可以轻松地看到这种对偶性。

然而，许多解决背包问题的实用算法都依赖于一个假设，即你能承受的重量与你可以选择的总重量相比较小。例如，动态规划 0/1解决方案依赖于循环直到达到最大重量，而FPTAS解决方案保证在总重量的(1-e)倍因子内是正确的（但庞大值的小因子仍然可能产生相当大的差异）。

因此，在需要的重量很大时，两者都存在问题。

因此，我想知道是否已经有人研究过“双背包问题”（如果可以找到相关文献），或者是否存在某些现有算法的简单修改方法我没有注意到。

- sanderd17

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- j_random_hacker · Accepted Answer

通常用于解决背包问题的伪多项式DP算法，对于每个i和w，会问：“如果我最多使用w容量，从前i个物品中可以获得的最大总价值是多少？”

相反，你可以问对于每个i和w，“如果我至少使用w容量，从前i个物品中可以获得的最小总价值是多少？” 逻辑几乎相同，只是比较的方向相反，并且需要一个特殊的值来记录即使拿走前i个物品也无法达到w容量的可能性--无穷大可以胜任此任务，因为当与min()进行比较时，你希望这个值输给任何有限值。