所有可能的团队名册算法？可能跟背包差不多？

Question

我做了一个业余爱好项目有一段时间了，这个项目包括在工资帽和球员职位限制的情况下找到所有可能的球队名单，同时尝试最大限度地发挥自己的潜力。这是专门针对梦幻足球的，但是这个问题可以更概括为一个最大化问题。我找不到比使用嵌套for循环更有效的解决方案了。我使用python字典按位置qbs[playerName] = {Salary: X, Projection: Y}和{}等位置跟踪特定的播放器数据

约束条件如下：

• 1个四分卫（qb）
• 2个退刀（rb1，rb2）
• 3个宽接收机（wr1， wr2，wr3）
• 1紧端（te）
• 1防御（dst）
• 1个flex播放器（可以是 向后跑、末端紧或接收器宽）
• 工资总额必须是 <；=N

我的算法的一般形式如下：

def optimize(teams):
    for qb in qbs:
        iter_rb = itertools.combinations(rbs,2)
        for rb1, rb2 in iter_rb:
            iter_wr = itertools.combinations(wrs,3)
            for wr1, wr2, wr3 in iter_wr:
                for te in tes:
                    for dst in dsts:
                        baseSalary = qb['Salary'] + rb1['Salary'] + rb2['Salary'] + wr1['Salary'] + wr2['Salary'] + wr3['Salary'] + te['Salary'] + dst['Salary']
                        baseProjection = qb['Projection'] + rb1['Projection'] + rb2['Projection'] + wr1['Projection'] + wr2['Projection'] + wr3['Projection'] + te['Projection'] + dst['Projection']
                        if baseSalary <= maxSalary:
                            for rb3 in rbs:
                                salary = baseSalary + rb3['Salary']
                                if salary <= maxSalary:
                                    projection = baseProjection + rb3['Projection']
                                    if projection > teams[-1].projection:
                                        insertTeamAndReorderList()
                            for wr4 in wrs:
                                salary = baseSalary + wr4['Salary']
                                if salary <= maxSalary:
                                    projection = baseProjection + wr4['Projection']
                                    if projection > teams[-1].projection:
                                        insertTeamAndReorderList()
                            for te2 in tes:
                                salary = baseSalary + te2['Salary']
                                if salary <= maxSalary:
                                    projection = baseProjection + te2['Projection']
                                    if projection > teams[-1].projection:
                                        insertTeamAndReorderList()
    return teams

我觉得有一个更优化的解决方案，但我就是想不出更多的优化？即使在切割wrs和{}时，这仍然需要几个小时才能运行。在

如果您有任何想法，或者确认没有更有效的解决方案，我们将不胜感激。谢谢！在

编辑：为了澄清，我再次在dst循环中遍历wrs、tes和rbs来搜索flex播放器。这大大减少了搜索空间，而不是所有flex合格玩家的列表。在

Answer 1

这看起来像是mathematical optimization或constraint programming问题。有许多库可以帮助您有效地解决这些类型的问题（分别参见here和here）。在

Answer 2

好的，按要求，这是我的MIP模型，可以找到最好的团队。在

注意，minpos和{}说明了每个位置需要多少球员。对于qb我们有1 <= y(qb) <= 1，但是对于rb：2 <= y(rb) <= 3等等。集合plpos表示玩家可以在哪个位置上比赛。在

现在，为了找到其他解决方案，我们可以使用一些最先进的解算器所拥有的工具（例如，Cplex有一个解决方案池技术），或者我们可以实现以下算法：

1. 求解模型
2. 如果有足够的解决方案：停止
3. 向禁止当前解决方案的模型添加一个约束（cut）
4. 转到步骤1

这个伤口看起来怎么样。让j是在解决方案中选择的一组玩家，即使用x*(j)=1。（应该有9个）。然后切割看起来像：sum_j x(j) <= 8。在算法的每一轮之后，我们添加一个新的切割（因此问题变得越来越大）。以上算法的每次迭代都会给您一个新的、唯一的、最佳的解决方案。在

一组解决方案可以看起来像：