最近我的一个朋友提出要解决一个简单的问题，我正在努力寻找最好的算法来解决它。
有一个运动员列表，每个运动员都有一个名字，一个体重，可以有多个角色，至少1个最多3个(Internal, Median和External)(.一个队由6名运动员组成(2个内部值，2个中值，2个外部值)。还有一个重量限制是540公斤。
找到这个问题的所有可能组合的最佳算法是什么?
现在我发现所有的组合遍历运动员列表，所有的角色，并删除所有超过限制的组合。
你有没有更好的算法来解决这个问题?解决这类问题的最佳方法是什么?
谢谢
找出所有可能组合的最佳算法是什么对于这个问题?
在最坏的情况下，如果你有n >= 6运动员，每个人的体重都很轻，所以限制无关紧要，每个人都能扮演所有角色，即使你不想乘法计算拥有相同角色的球员的球队，球队的数量也会增长得非常非常快。
在这种情况下确切的数字是"n选择6;或:
n * (n - 1) * (n - 2) * (n - 3) * (n - 4) * (n - 5) / 720
这是一个O(n6)问题。不管n大于30，这个都会变慢。一旦n > 123，数量将不再适合无符号32位整数。
如果团队规模可以变化，那么问题是O(nk)，其中k是团队规模。这不再是多项式;事实上，它比NP-Complete更难。[1]
对背包问题的解，它是# P完全的。因此，这是一个工程问题而不是算法问题。
现在我发现所有的组合遍历运动员列表，它的所有角色，并删除所有超过限制的组合。
这几乎就是我要做的，只有你可以通过尽可能早地修剪部分团队来提高效率。以下是我的一些想法:
- 按体重对运动员列表进行排序，以便当您超过体重限制时，您可以停止查看列表中较晚的运动员。
- 跟踪有多少角色有一个可能的运动员来完成他们，给定部分团队。当你到达第五个成员时，你知道运动员必须在一个人手不足的角色中扮演一个角色。
- 例如，如果你有一个由四名运动员组成的团队，到目前为止没有中值玩家，你必须只考虑下两个的中位数玩家。
- 为了使这更容易，为每个角色创建(排序)辅助列表，其中包含可以拥有该角色的玩家的指针。