0

我一直在研究这个问题的算法，但无法弄清楚。问题如下：

在与 X 球员的比赛中，每个球员都在赌 NBA 篮球比赛的结果。

猜对比赛结果的玩家得 3 分，猜对比赛的 MVP 得 1 分，猜错的都得 0 分。

该算法需要能够确定某个玩家是否无法达到该投注游戏中的第一名。

例如，假设联盟总共有 30 场比赛，那么玩家猜对的最高分是 (3+1)*30=120。

在下表中，您可以看到球员 X、Y 和 Z。球员 X 到目前为止猜对了 20 场比赛，因此他得了 80 分。玩家 Y 和 Z 分别得到 26 和 15 分，由于只剩下 10 场比赛，即使他们猜对了剩下的 10 场比赛，也不足以到达第一名。因此，算法确定他们被淘汰出局。

团队 积分 每场比赛得分 游戏总数 最高点数 剩下的比赛 可用积分 消除？
X 80 0-L 1-MVP 3-W 30 120 10 0-40 ñ
是 26 0-L 1-MVP 3-W 30 120 10 0-40 是
Z 15 0-L 1-MVP 3-W 30 120 10 0-40 是

棒球淘汰问题似乎与这个问题最相似，但并非完全如此。

我应该如何建立最大流量问题的减少来适应这个问题？

谢谢你。

4

1 回答 1

1

我不明白您为什么要研究非常复杂的最大流量算法。这些可能是非常复杂的事情所需要的（尤其是当配对导致零和结果并且顺序/剩余配对开始变得重要时->！非常！更难进行最坏情况分析）。

也许您提到的棒球问题就是其中之一（没有检查）。但是您的用例听起来微不足道。

1. Get current leader score LS
2. Get remaining matches N
3. For each player P
  4. Get current player score PS
  5. Eliminate iff PS + 3 * N < LS

(assumes parallel progress: standings always synced to all players P have played M games
 -> easy to generalize though)

这很简单。鉴于您的描述，没有什么可以阻止我们从所有其他玩家那里得出最坏情况的表现，也就是说，这是一个有效的场景，即所有其他玩家对所有即将到来的猜测都猜错了-> 玩家 P 的得分 S 可以在所有剩余的游戏中保持在 S 。

当存在更复杂的侧面约束（例如统计分布/期望）时，事情可能会迅速转变为 NP-hard 决策问题

于 2020-12-23T17:23:18.353 回答