我正在设计一个应用程序，通过组建最好的团队来帮助用户创建游戏。
例如，假设有 30 人在投票中等待打篮球。一场篮球比赛由 10 名球员（5 对 5）进行。在等待被选中的 30 人中，该算法会选择 5 对 5 的最佳组合来进行对战。
（为此，该算法会寻找有最大平局概率的玩家组合。这是通过使用表征每个玩家的两个量词来计算的：玩家的平均技能和猜测评分的置信度因子。）
我想看看这个算法有多快。
它需要经过所有可能的玩家组合。所以在这种情况下，组合的总数是 C(30,10) 对吗？？
我们可以说算法是 O(n!)，其中 n 是等待玩的玩家总数吗？
这个问题是NP完全的吗？如果是这样，谁能给我一个简短的方法来解释为什么它是 NP 完全的（不是完整的证明，只是一个有效的推理就足够了。）
非常感谢你 ！:)
目前尚不清楚如何将平均技能和置信度因素结合起来，但很可能在两者中找到多项式解决方案n（k球员人数和每队球员人数）就像证明 P = NP 一样困难。
我的直觉是基于子集和问题是 NP-Hard 的事实，而当前的问题似乎比它更难。
在我们的例子中，即使是一个简单的方法，它会忽略信心因素，而只是总结球员的技能以获得团队实力（1），它似乎是 NP-Complete 的。
那是因为即使我们固定了一支球队，即知道目标总和，也很难确定是否有另一支球队得分相同（2）。此外，回答“是否存在平等的团队？”这个问题。比回答“哪支球队最适合？”更容易。
此外，在所有成对的团队中找到最佳匹配可能比在一个固定的团队中找到最佳匹配更难，因此这将直观地证明给定问题比子集和问题更难。
评论：
(1) 以任何方式考虑置信度因素都不可能简化问题（因为在它们都相等的特定情况下，我们仍然会遇到不相关的置信度因素的情况）。
(2) 在子集和问题中，不对子集大小做出任何假设。然而，如果有一个已知的多项式时间算法可以在任何给定大小的多项式时间内找到一个总和为 0 的子集，我们可以将它应用于每个可能的大小，这将导致一个任意大小的多项式算法（这将证明 P = NP)。
(3) sum = 0 约束中的值 0 不是必需的。它可以是任意值。例如，因为我们固定了大小，我们可以简单地从所有元素中减去一个等于 targetSum / size 的值，我们现在将搜索总和为 0 的子集。
关于其他问题：
那么在这种情况下，组合的总数是 C(30,10) 对吗？
不，它实际上是 C(30, 5) * C(25, 5) / 2，因为我们首先需要为一队挑选 5 名球员，然后从其余的球员中挑选 5 名球员为二队。执行除以二是因为否则每对将被计算两次，我们可能不想区分团队。
我们可以说算法是 O(n!)，其中 n 是等待玩的玩家总数吗？
蛮力枚举的复杂度为 O(n^2k / (k! * k!))，其中 n 是玩家总数，k 是团队规模。因此，对于小的k它是可以的。n如果我们同时考虑和k作为变量，该方法是 NP 完全的。
复杂性是这样的，因为组合的公式如下：
C(n, k) = n * (n - 1) * .. * (n - k + 1) / (1 * 2 * .. * k),
并且根据上一点，有C(n, k) * C(n - k, k) / 2种可能。