在线算法-滑雪租赁

Question

我正在尝试解决一个在线算法，如滑雪租赁问题，但问题有点不同。

问题是我有N个盒子，每个盒子里有M个硬币，其中X

我的目标是选择一个盒子，以便最大限度地增加硬币的数量。

我的算法是选择一个参数G，打开第一个框，如果硬币数量大于G，就选择那个框，如果没有选择任何一个，我无论如何都会选择最后一个。

针对离线解决方案优化竞争定额的G应该是什么

Answer 1

如果你知道你有N个框，你可以选中前N/e框(e=2.7...)，并跟踪最大框(跳过所有框只查找最大值)现在你的G=Maximum大小，在选择大于G的第一个框之后，或者如果没有框选择最后一个。

正如Chris在他的评论中提到的，这是Secretary Problem，我提供的方法是这个问题的最佳解决方案，你可以在link中看到更多细节，但我不知道我们是否有给定的算法，选择G意味着什么？它取决于输入分布和一些附加信息。

Answer 2

如果你设置了一个常数G，你必须假设你的数据是由知道它的对手准备的。他们可以给你一个盒子，让你选择它，然后让最后一个盒子包含Y，从而使离线算法Y/G倍更有利可图。他们可以给你一个盒子，让你拒绝它，然后让最后一个盒子包含X，从而使离线算法G/X倍更有利可图。那么最不好的G似乎是sqrt(XY)，在这种情况下，离线算法的利润是sqrt(Y/X)的两倍。

你有没有在收到盒子之前随机选择G的选项，在这种情况下，你的对手只知道它的分布？基于X= 1的简单示例的有希望的行为，然后我会在ln X和ln Y之间随机选择ln G，但对于这种情况可能有更好的解决方案。找到它们的一种方法是只考虑离散值-这可能是本例中的实际情况，然后将情况视为您和您的对手之间的零和游戏。