我正在尝试解决像滑雪设备租赁问题这样的在线算法，但问题有点不同。
问题是我有 N 个盒子，每个盒子里有 M 个硬币，其中 X < M < Y 并且在每个不同的盒子里可以不同。我可以选择一个盒子并检查硬币数量，我必须决定是选择这个盒子还是跳过它(注意如果我跳过它，我以后不能再回到这个盒子)。
我的目标是选择一个盒子以使硬币数量最大化。
我的算法是选择一个参数 G，然后打开第一个框，如果硬币数量大于 G，则选择那个框，如果没有选择任何一个，我还是选择最后一个。
G 应该是什么来优化与离线解决方案的竞争比
最佳答案
如果你知道你有 N 个框，你可以先检查 N/e 个框(e=2.7...)，并跟踪最大框(跳过所有框只找到最大值)现在你的 G = 最大尺寸，之后选择第一个大于 G 的框，如果没有框则选择最后一个。
正如 Chris 在他的评论中提到的，这是 Secretary Problem我提供的方法是这个问题的最佳解决方案，您可以在链接中看到更多详细信息，但我不知道如果我们有给定的算法，选择 G 意味着什么？它取决于输入分布和一些附加信息。
关于algorithm - 在线算法 - 雪具租赁，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7846897/