梦幻联赛梦之队算法？

Question

对于那些不熟悉FPL的人，这里有一个简短的版本。无论是守门员、后卫、中场球员还是前锋，你都有球员。每个玩家都有一些价格(或者四舍五入到.5或者.0)，并且根据他们的真实生活表现你可以得到分数。你有一个100 on的预算，你需要建立一个团队，记住你有一个限制球员在每个位置。

现在的问题是:如果你有所有球员的价格，他们的位置和他们在一个赛季中得分的总数，你如何找到得分最高的球队，比如4-4-2阵型？(1 1GK，4 4DEF，4 4MID，2 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}