<p>正如评论中提到的,这是一个约束满足问题。它有一个组合部分,但由于您没有定义最小化或最大化的目标,所以它不是一个优化问题(还没有)。你可以用很多方法来解决这个问题:你可以尝试像piRSquared这样的暴力,或者使用像pm2ring这样的启发式算法。我将提出一个0-1线性规划的解决方案,并使用<a href="https://pypi.python.org/pypi/PuLP" rel="nofollow noreferrer">PuLP</a>库来建模和解决问题。在</p>
<pre><code>from pulp import *
import pandas as pd
df = df.set_index('Name')
feasible_solutions = []
</code></pre>
<p>为了对问题建模,首先需要定义决策变量。这里,决策变量将是每个玩家的指示变量:如果选择了该玩家,则为1,否则为0。下面是如何在纸浆中做到这一点:</p>
^{pr2}$
<p>接下来,您将创建一个问题:</p>
<pre><code>prob = pulp.LpProblem('Team Selection', pulp.LpMinimize)
</code></pre>
<p>正如我前面提到的,你的问题没有说明任何目标。你只想创建所有可能的团队。因此,我们将定义一个任意目标函数(我将再次回到这个任意函数)。在</p>
<pre><code>prob += 0
</code></pre>
<p>主要有两个约束:</p>
<p>1)球队将有5名球员:</p>
<pre><code>prob += lpSum([players[player] for player in players]) == 5
</code></pre>
<p>记住,玩家字典存储我们的决策变量。<code>players[player]</code>为1(如果该玩家在团队中)或0(否则)。因此,如果你把它们加起来,结果应该等于5。在</p>
<p>2)工资总额应在45k到50k之间</p>
<pre><code>prob += lpSum([players[player] * df.at[player, 'Salary']
for player in players]) <= 50000
prob += lpSum([players[player] * df.at[player, 'Salary']
for player in players]) >= 45000
</code></pre>
<p>这与第一个约束类似。在这里,我们不计算工资,而是将工资相加(当球员在队中时,该值将为1,因此将乘以相应的工资。否则,值将为零,乘法也将为零)。在</p>
<p>主要建模在这里完成。如果您调用<code>prob.solve()</code>,它将找到满足这些约束的<em>解决方案。通常,在优化问题中,我们提供一个目标函数,并试图使其最大化或最小化。例如,假设你有玩家技能的分数。你的预算是有限的,你不能继续选择前5名球员。因此,在我们所说的<code>prob += 0</code>的部分中,您可以定义一个目标函数来最大化总技能分数。但那不是你想要的,所以我们继续吧。在</p>
<p>找到解决方案后,可以向问题添加另一个约束,声明下一个解决方案应该与此不同,您可以生成所有解决方案。在</p>
<pre><code>while prob.solve() == 1:
current_solution = [player for player in players if value(players[player])]
feasible_solutions.append(current_solution)
prob += lpSum([players[player] for player in current_solution]) <= 4
</code></pre>
<p><code>prob.solve()</code>是解决问题的方法。基于结果,它返回一个整数。如果找到一个最优解,结果是1。对于不可行或无限解,有不同的代码。所以只要我们能找到新的解决方案,我们就继续循环。在</p>
<p>在循环中,我们首先将当前解决方案附加到<code>feasible_solutions</code>列表中。然后,我们添加另一个约束:对于这5个玩家,变量之和不能超过4(最大值5,如果是5,我们知道这是相同的解)。在</p>
<p>如果你运行这个,你会得到和piRSquared相同的结果。在</p>
<p><a href="https://i.stack.imgur.com/XxpkU.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/XxpkU.png" alt="enter image description here"/></a></p>
<p>那么,这有什么好处呢?在</p>
<p>我们使用整数/二进制线性规划的主要原因是组合的数量增长非常快。这叫做<a href="https://en.wikipedia.org/wiki/Combinatorial_explosion" rel="nofollow noreferrer">combinatorial explosion</a>。看看可能的团队数量(没有任何限制):</p>
<pre><code>from scipy.misc import comb
comb(10, 5)
Out: 252.0
comb(20, 5)
Out: 15504.0
comb(50, 5)
Out: 2118760.0
comb(100, 5)
Out: 75287520.0
</code></pre>
<p>几乎不可能评估所有的组合。在</p>
<p>当然,当你想列出满足这些约束的所有组合时,你仍然在冒这个风险。如果满足约束条件的组合数量很大,则需要花费大量时间进行计算。你无法避免。但是,如果这个子集很小或者仍然很大,但是你正在计算这个集合上的一个函数,它会更好。在</p>
<p>例如,考虑以下数据帧:</p>
<pre><code>import numpy as np
np.random.seed(0)
df = pd.DataFrame({'Name': ['player' + str(i).zfill(3) for i in range(100)],
'Salary': np.random.randint(0, 9600, 100)})
</code></pre>
<p>75287520个解决方案中有268个满足薪资限制。在我的电脑里花了44秒才把它们列出来。用暴力手段找到他们需要几个小时(更新:It需要8小时21分钟)。在</p>
<p>默认情况下,PuLP使用开源解算器<a href="https://projects.coin-or.org/Cbc" rel="nofollow noreferrer">Cbc</a>。还有其他开源/商业替代解决方案可以与PuLP一起使用。商业化的通常比预期的更快(尽管它们非常昂贵)。在</p>
<p>另一种选择是我在评论中提到的约束编程。对于这类问题,您可以找到许多聪明的方法,通过约束编程来减少搜索空间。我对整数编程很满意,所以我展示了一个基于此的模型,但是我应该注意到约束编程可能会更好。在</p>