algorithm - 双背包算法

Question

假设您有一个存放易碎元素(例如蔬菜或水果)的仓库，并且您只能取出一次装有蔬菜的容器。如果你移动它们两次，它们会腐烂得太快而无法再出售。

因此，如果您为每个容器的蔬菜赋予值(value)(取决于它们的保鲜时间)，您希望首先出售值(value)最低的。当客户要求一定的重量时，您希望提供良好的服务，并给出准确的重量(因此您需要从仓库中取出一些额外的重量，并在销售后丢弃多余的重量)。

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

您可以很容易地看到这种二元性，将仓库视为背包，并将仓库的最大值和有限重量优化为最大当前重量减去客户要求的重量。

但是，许多解决背包问题的实用算法都依赖于这样的假设:与您可以选择的总重量相比，您可以携带的重量较小。 F.e. dynamic programming 0/1解决方案依赖于循环直到达到最大重量，并且 FPTAS解决方案保证在总权重的 (1-e) 因子内是正确的(但一个巨大值的小因子仍然可以产生相当大的差异)。

所以当需要的重量很大时，两者都会有问题。

因此，我想知道是否有人已经研究过“双背包问题”(如果可以找到一些相关文献)，或者是否对我遗漏的现有算法进行了一些简单的修改。

Answer 1

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

您可以改为问，对于每个 i 和 w，“如果我至少使用 w 个容量，我可以从前 i 个项目中获得的最小总值(value)是多少？”逻辑几乎相同，只是比较的方向是相反的，你需要一个特殊的值来记录即使把前 i 项中的所有 i 项也不能达到 w 容量的可能性——无穷大适用于此，因为你想要与 min() 进行比较时，此值相对于任何有限值都会丢失。