algorithm - 梦幻英超梦之队算法？

Question

对于那些不熟悉 FPL 的人，这里有一个简短的版本。你有球员扮演守门员、后卫、中场或前锋。每个球员都有一些价格(四舍五入为 .5 或 .0)，并且根据他们在现实生活中的表现，您可以获得积分。你有 100 英镑的预算，你需要组建一支球队，请记住你对每个位置的球员都有限制。

现在，问题是:如果你有所有球员的价格、他们的位置和他们在一个赛季中的总得分，你如何找到得分最高的球队，例如 4-4-2编队？ (1GK, 4DEF, 4MID, 2FWD)

我想这是背包问题的一个变体，你有限制只能有 11 名球员，并且正好是 4-4-2 阵型。那么这是解决这个问题的最佳方法吗？您将如何通过这些修改/限制来解决它，或者是否有更好的解决方案？

Answer 1

将问题表述为整数规划并使用您最喜欢的 IP 求解器(例如 https://www.gnu.org/software/glpk/)求解。

对于每个玩家 p，该公式有一个 0-1 决策变量 x_p 如果该玩家在团队中则为 1。

maximize sum_{p in players} points-scored(p)
subject to
sum_{p in players} price(p) x_p <= 100
sum_{p in goalkeepers} x_p <= 1
sum_{p in defenders} x_p <= 4
sum_{p in midfielders} x_p <= 4
sum_{p in forwards} x_p <= 2
for all p in players, x_p in {0, 1}