有效地解决在线未加速的0-1背包问题

Question

我有 $ n $ 项目和一个大小的bin $ b $ 单位。每个项目 $ j $ foodes $ w_j $ $ B $ 放入背包时。该物品以在线方式逐一出现。一旦出现了项目 $ i $ ，我们必须将其放入垃圾箱（不可撤销）或忽略它。目标是最大化放入箱中的物品数量。 （所有输入都是正整数。）

脱机算法简单：将项目放在顺序 $ w_1 \ leq w_2 \ leq \ cdots \ leq w_n $ 直到bin已满。

如何以在线方式解决此问题？我的方法是随机化选项：一旦项目 $ j $ 出现，将它放入概率 $ p_j $ < / span>否则忽略它。

Answer 1

好像你已经注意到，或者至少没有提到，很容易看出没有确定的竞争算法的问题。（Consterexamples只需要两个项目，您可以使用算法确定性的事实。）

您的方法采取随机化实际上是不够的，因为随机化无法克服一些困难。但是你的问题有一些放松模型。

其中一些，以及我的答案的一些细节可以通过Susanne Albers，Arindam Khan和Leon Ladewig命名为“改进的在线算法，随机顺序模式改进的在线算法”（参见第1.1节）。