1

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

我可以选择的球员有一个限制：我最多只能从俱乐部中选择 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

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

任何帮助将非常感激。

最好的，

4

1 回答 1

2

它可以通过最小成本流问题来解决，这是匈牙利算法解决的问题的概括。

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

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

于 2013-07-16T12:02:57.857 回答