algorithm - 算法。从各种可能性中挑选最佳组合

Question

我必须解决以下问题，基本上是从可能的组合中选出一个最佳组合(巨大)——我必须从可能的球员中选出一个最好的足球队，每个球员都有一个分数，我必须选择在选定球员中总分最高的球队。

我可以选择的球员有一个限制:我最多只能从一个俱乐部中挑选 N(例如 =2)名球员。例如，如果我选择 G1(来自切尔西)作为守门员，那么切尔西只剩下 1 个名额。

假设我必须选择 1-4-4-2 的最佳阵型

守门员(1):g1、g2、g3、g4 ...(该位置球员姓名，得分分别为gc1、gc2、gc3、gc4 ...)

防御者 (4):d1、d2、d3、...

中场 (4): m1, m2, m3, ...

前锋 (2): s1, s2, s3, s4, ...

我可以在这里使用什么算法？我在看所谓的匈牙利算法: http://en.wikipedia.org/wiki/Hungarian_algorithm

但它看起来很复杂，不确定是否适合这种情况。

如有任何帮助，我们将不胜感激。

最好的，

Answer 1

可以通过 minimum-cost flow problem 解决，匈牙利算法解决的问题的推广。

创建一个网络，其中 (1) 每个俱乐部一个节点 (2) 每个球员一个节点 (3) 每个空缺职位一个节点。每个俱乐部节点提供两个单位的流量，每个开放位置节点吸收单位等于该位置需要的玩家数量。每个这样的关系都有俱乐部到球员的弧线，容量为一，成本为零。也有球员到空位的弧线，容量为 1，成本等于减去该球员在该位置的值(value)(如果像梦幻美式足球那样有“弹性”点，则可能涉及一名球员的多个这样的弧线)。

找到值(value) 11 的最小成本积分流。每个玩家都用作零或一个流量单位的中转站。最好的团队由后者组成。