确定一组组合的最高分数

Question

我在用python编程。在

我有以下表格的数据：

(A, B, C, D, E, F, G, H, I)

此数据段与分数相关联，例如：

^{pr2}$

我们可以对这些数据进行评分，如下所示：

A B C E + D F G + H I = .77 * .6 * .55 = 0.2541

另一种可能性是：

A B C D + E F G + H + I = .99 * .79 * .09 * .03 = 0.00211167

所以，第一个组合给出了更高的分数。在

我想写一个算法来建立高于最高分数的数据。数据成员的重复次数不应超过一次。换句话说：

A B C E + E F G + D + H I 

无效。你建议我怎么解决这个问题？在

谢谢

巴里

编辑： 我应该澄清（H，I）！=（I，H）和那个（I，H）不是ABCDEFGHI的一个子段，而是ABIHJ的一个子段。 另一件事我应该提到的是分数是一个非常大的集合（百万），我们计算分数的部分的平均长度约为10。此外，我计算分数的方式将来可能会改变。也许我想把这些子段加起来，取平均值而不是乘以，谁知道。。。因此，最好将计算可能的组合的代码与实际的分数计算分开。目前，我倾向于认为工具组合可能是个好的起点。在

Answer 1

这听起来像是一个伪装的NP完全问题，是Knapsack problem的派生。这就意味着你可能要走遍所有的可能性来得到一个精确的答案。在

尽管。。。等待。值介于0和1之间。也就是说结果只能越小越好，最多只能保持相等。因此，解决方案很简单：获得具有最高值的单个组，然后处理。（我知道这可能不是您想要的，但您可能需要添加另一个条件，例如，必须使用所有元素….？）在

暴力手段的开始：

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])

现在，创建所有2^（num segments）可能的片段组合，检查每个组合是否有效，如果有效，则计算分数，同时保留当前赢家及其最高分数。只是一个起点。。。在

好吧，再做一次更新：这里有很多空间进行优化，特别是因为你在乘法（我假设现在你必须使用每个元素）。在

• 因为你的总分永远不会增加，所以你可以放弃任何低于当前最高分数的探索路径[segment0，segment1]，因为你只能在任何一段2中获得作品。

• 如果您不只是迭代所有的可能性，而是从搜索包含第一个片段的所有片段列表开始（通过递归地搜索除第二个片段之外还包含的所有片段列表等），您可以在第一个和第二个片段无效时立即断开，i、 e.无需探索所有分组的可能性（A，B，C，D）和（A，B，C，D，e）

• 由于伤害成倍增加，尽量减少分段的数量可能是一个合适的启发，所以从分数较高的大片段开始。

Answer 2

暴力强制，通过使用递归（对每个分段按顺序，我们递归地找到使用分段的最佳分数，而不使用分段的最佳分数。如果剩余项目没有可能的分段组合，则得分为0）：

segment_scores = (('A', 'B', 'C', 'D'), .99), (('A', 'B', 'C', 'E'), .77) #, ...

def best_score_for(items, segments, subtotal = 1.0):
    if not items: return subtotal
    if not segments: return 0.0
    segment, score = segments[0]
    best_without = best_score_for(items, segments[1:], subtotal)
    return max(
        best_score_for(items.difference(segment), segments[1:], subtotal * score),
        best_without
    ) if items.issuperset(segment) else best_without

best_score_for(set('ABCDEFGHI'), segment_scores) # .430155

Answer 3

首先，我建议给有意义的片段分配一个独特的符号。在

然后你可能需要这些符号的组合（或者也许是排列，我相信你比我更了解你的问题），以及一个“合法的分段组合”函数，你可以用它来排除不好的可能性——基于矩阵，哪些是冲突的，哪些不冲突的

>>> import itertools
>>> itertools.combinations([1,2,3,4], 2)
<itertools.combinations object at 0x7fbac9c709f0>
>>> list(itertools.combinations([1,2,3,4], 2))
[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
>>>

然后最大化使其通过合法的\u segment_combination（）的有效可能性。在