从一系列对象中找到所有组合的算法

Question

最近，我的一个朋友建议解决一个简单的问题，我很难找到解决问题的最佳算法。

有一个运动员的列表，每个运动员都有一个名字，一个重量，并且可以具有多个角色，至少有1个最多1个（内部，中位数和外部）。 一支球队由6 运动员组成（2个内部分子，2个中位数和2个外部）。 还有一个重量限制为540公斤。

找到解决此问题的所有可能组合的最佳算法是什么？

现在，我发现所有组合都在运动员名单，所有角色以及删除所有限制的组合中都进行了迭代。

您有更好的算法可以解决此问题吗？ 解决此类问题以解决它的最佳方法是什么？

谢谢

Answer 1

对于此问题，找到所有可能组合的最佳算法是什么？

在最坏的情况下，您拥有n＆gt; = 6运动员，每个人的权重少，以至于极限无关紧要，每个人都能扮演所有角色，所以团队的数量成长非常非常，很快，即使您不想将具有相同球员的球员分配给不同角色的团队。

在这种情况下，确切的数字是“ n选择6”或：

n * (n - 1) * (n - 2) * (n - 3) * (n - 4) * (n - 5) / 720

这是O（n ⁶ ）问题。如果n大于30。 123 ，该数量不再适合未签名的32位整数。

如果团队的大小可能有所不同，则问题是O（n ^k ），其中k是团队的大小。这不再是多项式；实际上，它比np-complete更难。它将能够枚举解决方案 knapsack问题 IS [1]

因此，这是一个工程问题，而不是算法问题。

现在，我发现所有组合都通过运动员名单，所有角色并删除了限制限制的所有组合。

这几乎是我要做的，只有您可以尽早修剪部分团队来使其更有效。我有一些想法：

1. 按重量排序运动员名单，以便当您超出体重限制时，您可以停止查看名单中的后来的运动员。
2. 鉴于党派团队，请跟踪有多少角色可以实现他们。当您到达第五成员时，您知道运动员必须在其中一个短角色中扮演角色。
   1. 例如，如果您到目前为止有四个运动员的团队，没有中位数球员，则必须仅考虑接下来的两个球员。
   2. 为了使这一点更容易，为每个角色的角色创建（排序）辅助列表，这些角色包含指向可以具有该角色的玩家的指针。