<p>这听起来像是一个伪装的NP完全问题,是<a href="http://en.wikipedia.org/wiki/Knapsack_problem" rel="nofollow">Knapsack problem</a>的派生。这就意味着你可能要走遍所有的可能性来得到一个精确的答案。在</p>
<p>尽管。。。等待。值介于0和1之间。也就是说结果只能越小越好,最多只能保持相等。因此,解决方案很简单:获得具有最高值的单个组,然后处理。(我知道这可能不是您想要的,但您可能需要添加另一个条件,例如,必须使用所有元素….?)在</p>
<p>暴力手段的开始:</p>
<pre><code>import operator
segment_scores = {(A, B, C, D): .99, (A, B, C, E): .77} #...
def isvalid(segments):
"""returns True if there are no duplicates
for i in range(len(segments)-1):
for element in segments[i]:
for j in range(len(segments)-i-1):
othersegment = segments[j+i+1]
if element in othersegment:
return False
return True
better way:
"""
flattened = [item for sublist in segments for item in sublist]
# http://stackoverflow.com/questions/952914/making-a-flat-list-out-of-list-of-lists-in-python
return len(set(flattened)) == len(flattened)
def getscore(segments):
"""
p = 1.0
for segment in segments:
p *= segment_scores[segment]
return p
better way:
"""
return reduce(operator.mul, [segment_scores[segment] for segment in segments])
</code></pre>
<p>现在,创建所有2^(num segments)可能的片段组合,检查每个组合是否有效,如果有效,则计算分数,同时保留当前赢家及其最高分数。只是一个起点。。。在</p>
<p>好吧,再做一次更新:这里有很多空间进行优化,特别是因为你在乘法(我假设现在你必须使用每个元素)。在</p>
<ul>
<li><p>因为你的总分永远不会增加,所以你可以放弃任何低于当前最高分数的探索路径[segment0,segment1],因为你只能在任何一段2中获得作品。</p></li>
<li><p>如果您不只是迭代所有的可能性,而是从搜索包含第一个片段的所有片段列表开始(通过递归地搜索除第二个片段之外还包含的所有片段列表等),您可以在第一个和第二个片段无效时立即断开,i、 e.无需探索所有分组的可能性(A,B,C,D)和(A,B,C,D,e)</p></li>
<li><p>由于伤害成倍增加,尽量减少分段的数量可能是一个合适的启发,所以从分数较高的大片段开始。</p></li>
</ul>