双背包算法
Dual knapsack algorithm
假设你的仓库里有易碎品（f.e.蔬菜或水果），你只能取出一次装有蔬菜的容器。如果你移动它们两次，它们会腐烂得太快而无法再出售。
因此，如果您为每个容器的蔬菜赋予价值（取决于它们的保鲜时间），您希望首先出售价值最低的蔬菜。而当客户要求一定的重量时，你想提供好的服务，并给出准确的重量（所以你需要从你的仓库中取出一些额外的东西，然后卖掉多余的部分）。
我不知道这个问题是否有名字，但我认为这是背包问题的对偶形式。在背包问题中，您希望最大化价值并将重量限制为最大值。而在这里你想最小化该值并将权重限制到最小值。
你可以很容易地看到这种二元性，把仓库当作背包，优化仓库的最大值和限制重量，最大为当前重量减去客户要求的重量。
但是，许多解决背包问题的实用算法都依赖于这样的假设，即与您可以选择的总重量相比，您可以携带的重量较小。 F.e。 dynamic programming 0/1 solution relies on looping until you reach the maximum weight, and the FPTAS 解决方案保证在总重量的 (1-e) 因子内是正确的（但巨大值的一个小因子仍然可以产生相当大的差异）。
所以当想要的重量很大时，两者都会有问题。
因此，我想知道是否有人研究过 "dual knapsack problem"（如果可以找到一些相关文献），或者是否对我遗漏的现有算法进行了一些简单的修改。
解决背包问题的常用伪多项式 DP 算法要求，对于每个 i 和 w，"What is the largest total value I can get from the first i items if I use at most w capacity?"
你可以改为问，对于每个i和w，"What is the smallest total value I can get from the first i items if I use at least w capacity?"逻辑几乎相同，只是比较的方向是相反的，需要一个特殊的值来记录即使取的可能性前 i 项中的所有 i 项都不能达到 w 容量——无穷大适用于此，因为当与 min() 比较时，您希望该值相对于任何有限值丢失。
假设你的仓库里有易碎品（f.e.蔬菜或水果），你只能取出一次装有蔬菜的容器。如果你移动它们两次，它们会腐烂得太快而无法再出售。
因此，如果您为每个容器的蔬菜赋予价值（取决于它们的保鲜时间），您希望首先出售价值最低的蔬菜。而当客户要求一定的重量时，你想提供好的服务，并给出准确的重量（所以你需要从你的仓库中取出一些额外的东西，然后卖掉多余的部分）。
我不知道这个问题是否有名字，但我认为这是背包问题的对偶形式。在背包问题中，您希望最大化价值并将重量限制为最大值。而在这里你想最小化该值并将权重限制到最小值。
你可以很容易地看到这种二元性，把仓库当作背包，优化仓库的最大值和限制重量，最大为当前重量减去客户要求的重量。
但是，许多解决背包问题的实用算法都依赖于这样的假设，即与您可以选择的总重量相比，您可以携带的重量较小。 F.e。 dynamic programming 0/1 solution relies on looping until you reach the maximum weight, and the FPTAS 解决方案保证在总重量的 (1-e) 因子内是正确的（但巨大值的一个小因子仍然可以产生相当大的差异）。
所以当想要的重量很大时，两者都会有问题。
因此，我想知道是否有人研究过 "dual knapsack problem"（如果可以找到一些相关文献），或者是否对我遗漏的现有算法进行了一些简单的修改。
解决背包问题的常用伪多项式 DP 算法要求，对于每个 i 和 w，"What is the largest total value I can get from the first i items if I use at most w capacity?"
你可以改为问，对于每个i和w，"What is the smallest total value I can get from the first i items if I use at least w capacity?"逻辑几乎相同，只是比较的方向是相反的，需要一个特殊的值来记录即使取的可能性前 i 项中的所有 i 项都不能达到 w 容量——无穷大适用于此，因为当与 min() 比较时，您希望该值相对于任何有限值丢失。