<p>下面是我如何解决这个问题。不过,这是基于您的简单示例,对于更复杂的设置可能没有意义。在</p>
<p>假设工具的数量有限,取所有工具的组合(称之为“设置”),并确定每个设置可以完成哪些作业。在</p>
<p>然后搜索可以完成所有作业的设置组合,从长度1的组合开始,然后递增。在</p>
<pre><code>import itertools
num_stations = 3
tools = (
('hammer', 2),
('screwdriver', 4),
('nail gun', 6),
('wrench', 4),
('pillow', 5),
)
job_requirements = (
(('hammer', 2), ('screwdriver', 4)),
(('hammer', 2), ('nail gun', 6)),
(('hammer', 2), ('wrench', 4)),
(('wrench', 4), ('nail gun', 6)),
(('screwdriver', 4), ('pillow', 5)),
)
def satisfies_job(tools, job):
return all(tool in tools for tool in job)
setups = []
for comb in itertools.combinations(tools, num_stations):
# store this setup if no tool conflicts
if len(set(tool[1] for tool in comb)) == len(comb):
setups.append(comb)
# check increasing numbers of combinations of setups until all jobs can be performed
for num_setups in range(1, len(setups)):
for setups_comb in itertools.combinations(setups, num_setups):
# check if all jobs can be completed with this combination of tool setups
if all(any(satisfies_job(comb, job) for comb in setups_comb) for job in
job_requirements):
print 'found valid tool setup combination:'
for comb in setups_comb:
print comb
exit(0)
</code></pre>
<p>结果:</p>
^{pr2}$
<p>这将所有工具组合存储在内存中,因此随着工具数量的增加,可能会使用大量内存。它无疑是可以优化的,但应该提供一个起点。在</p>
<p><strong>编辑</strong></p>
<p>上面有一个bug,它需要包含<code>num_stations</code>的工具的设置,因此对于<code>num_stations = 5</code>它失败了,因为只有一个组合,但是它有冲突。为了纠正这个问题,它应该允许设置<em>最多</em><code>num_stations</code>工具:</p>
<pre><code># check increasing numbers of combinations of setups until all jobs can be performed
for num_setups in range(1, 1 + len(job_requirements)):
print('check combinations of %d setups' % num_setups)
setups = (c for c in chain(*(combinations(tools, i) for i in range(1, 1+num_stations)))
if len(set(tool[1] for tool in c)) == len(c))
for setups_comb in combinations(setups, num_setups):
# check if all jobs can be completed with this combination of tool setups
if all(any(satisfies_job(comb, job) for comb in setups_comb) for job in
job_requirements):
print 'found valid tool setup combination:'
for comb in setups_comb:
print comb
exit(0)
</code></pre>
<p>这还通过迭代设置的生成器来消除内存使用问题。在</p>