我正在尝试解决像滑雪租赁问题这样的在线算法，但是问题有点不同。
问题是我有N个盒子，每个盒子里有M个硬币，其中X
我的目标是选择一个盒子，使硬币的数量最大化。
我的算法是选择一个参数G，打开第一个盒子，如果硬币的数量大于G，则选择该盒子，如果没有选择任何硬币，则选择最后一个。
如何优化与离线解决方案的竞争比率
如果你知道你有N个盒子，你可以选中前N/e个盒子(e=2.7…)，并跟踪最大的盒子(跳过所有的只是找到最大值)现在你的G=最大尺寸，然后选择第一个大于G的盒子，或者如果没有盒子选择最后一个。
正如Chris在他的评论中提到的，这是秘书问题，我提供的方法是这个问题的最佳解决方案，你可以在链接中看到更多细节，但我不知道如果我们有一个给定的算法，选择G意味着什么?这取决于输入分布和一些附加信息。
如果您设置常数G，则必须假设攻击者知道您的数据。他们可以给你一个盒子，让你选择它，然后让最后一个盒子包含Y，这样使离线算法Y/G倍更有利可图。他们可以给你一个盒子，只会让你拒绝它，然后让最后一个盒子包含X，这样使离线算法的利润增加G/X倍。最小的坏G似乎是sqrt(XY)，在这种情况下，离线算法是sqrt(Y/X)倍更有利可图。
你是否可以在收到盒子之前随机选择G，在这种情况下，你的对手只知道它的分布?基于X = 1的简单例子，我将在ln X和ln Y之间均匀随机地选择ln G，但对于这种情况可能有更好的解决方案。找到它们的一种方法是只考虑离散值-这可能是本例中的实际情况，然后将这种情况视为您和对手之间的零和游戏。