算法：淘汰不再有机会赢得比赛的玩家
Algorithm: Eliminating players that no longer have a chance to win the tournament
我一直在研究这个问题的算法，但无法弄清楚。问题如下：
在有 X 名球员参加的锦标赛中，每位球员都在为 NBA 篮球比赛的结果下注。
猜对比赛结果的选手得 3 分，猜对比赛的 MVP 得 1 分，猜错得 0 分。
算法需要能够判断某个玩家是否无法在本次投注游戏中获得第一名。
例如，假设联赛共有30场比赛，则玩家猜对最多可获得的分数为(3+1)*30=120。
在下面的 table 中，您可以看到玩家 X、Y 和 Z。
玩家 X 到目前为止猜对了 20 场比赛，所以他有 80 分。
选手Y和Z分别有26分和15分，由于只剩下10场比赛，即使他们猜对了剩下的10场比赛，也不足以达到第一名的位置。
因此，算法判定他们被淘汰出局。
Team
Points
Points per match
Total Games
Max Points possible
Games left
Points Available
Eliminated?
X
80
0-L 1-MVP 3-W
30
120
10
0-40
N
Y
26
0-L 1-MVP 3-W
30
120
10
0-40
Y
Z
15
0-L 1-MVP 3-W
30
120
10
0-40
Y
The baseball elimination这个问题貌似和这个问题最像，其实不完全是
我应该如何减少最大流量问题来解决这个问题？
谢谢。
我不明白你为什么要研究非常复杂的最大流算法。对于非常复杂的事情可能需要这些（特别是当配对导致 zero-sum 结果并且 order/remaining 配对开始重要时 -> ！更难进行最坏情况分析）。
也许你提到的棒球问题就是其中之一（没有检查）。但是您的用例听起来 微不足道。
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 决策问题
我一直在研究这个问题的算法，但无法弄清楚。问题如下：
在有 X 名球员参加的锦标赛中，每位球员都在为 NBA 篮球比赛的结果下注。
猜对比赛结果的选手得 3 分，猜对比赛的 MVP 得 1 分，猜错得 0 分。
算法需要能够判断某个玩家是否无法在本次投注游戏中获得第一名。
例如，假设联赛共有30场比赛，则玩家猜对最多可获得的分数为(3+1)*30=120。
在下面的 table 中，您可以看到玩家 X、Y 和 Z。 玩家 X 到目前为止猜对了 20 场比赛，所以他有 80 分。 选手Y和Z分别有26分和15分，由于只剩下10场比赛，即使他们猜对了剩下的10场比赛，也不足以达到第一名的位置。 因此，算法判定他们被淘汰出局。
| Team | Points | Points per match | Total Games | Max Points possible | Games left | Points Available | Eliminated? |
|---|---|---|---|---|---|---|---|
| X | 80 | 0-L 1-MVP 3-W | 30 | 120 | 10 | 0-40 | N |
| Y | 26 | 0-L 1-MVP 3-W | 30 | 120 | 10 | 0-40 | Y |
| Z | 15 | 0-L 1-MVP 3-W | 30 | 120 | 10 | 0-40 | Y |
The baseball elimination这个问题貌似和这个问题最像，其实不完全是
我应该如何减少最大流量问题来解决这个问题？
谢谢。
我不明白你为什么要研究非常复杂的最大流算法。对于非常复杂的事情可能需要这些（特别是当配对导致 zero-sum 结果并且 order/remaining 配对开始重要时 -> ！更难进行最坏情况分析）。
也许你提到的棒球问题就是其中之一（没有检查）。但是您的用例听起来 微不足道。
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 决策问题