为一组组合确定最高分

5 投票

4 回答

1374 浏览

提问于 2025-04-17 09:02

我正在用Python编程。

我有以下格式的数据：

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

这些数据的每一部分都有一个分数，比如：

scores:

    (A, B, C, D) = .99
    (A, B, C, E) = .77
    (A, B, E) = .66
    (G,) = 1
    (I,) = .03
    (H, I) = .55
    (I, H) = .15
    (E, F, G) = .79
    (B,) = .93
    (A, C) = .46
    (D,) = .23
    (D, F, G) = .6
    (F, G, H) = .34
    (H,) = .09
    (Y, Z) = 1

我们可以通过以下方式为这些数据计算分数：

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。此外，我计算分数的方式可能将来会改变。也许我想添加子部分并取平均，而不是相乘，谁知道呢……因此，把计算可能组合的代码和实际计算分数的代码分开可能更好。目前，我倾向于认为 itertools.combinations 可能是一个不错的起点。

数据处理 itertools 复杂度分析算法设计分数计算组合优化数据组合不重复选择

4 个回答

首先，我建议给那些有意义的部分分配一个独特的符号。

接下来，你可能需要这些符号的组合（或者说排列，我相信你对自己的问题比我更了解），同时还需要一个“合法组合检查”的函数，用来排除那些不合适的可能性——这可以根据一个矩阵来判断哪些是冲突的，哪些不是。

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

然后，找出通过合法组合检查的有效可能性中最大的那一个。

回答于 2025-04-17 由 Python大师

分享举报

这听起来像是一个伪装的 NP 完全问题，实际上是背包问题的一种变体。这意味着你可能需要考虑所有可能的情况才能找到准确的解决方案。

不过等等，你的值在 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^(段数) 的可能组合，检查每个组合是否有效，如果有效，就计算得分，同时保持当前的赢家和它的高分。这只是一个起点……

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

由于你的总得分永远不会增加，你可以放弃任何低于当前高分的探索路径 [段0, 段1]，因为你只会得到任何段2 的结果。
如果你不是简单地遍历所有可能，而是从包含第一个段的所有段列表开始（通过递归探索包含第二个段的所有段列表，以此类推），那么一旦发现第一个和第二个段无效，就可以提前结束探索，比如不需要探索 (A,B,C,D) 和 (A,B,C,D,E) 的所有组合。
由于乘法运算会增加复杂度，尝试减少段的数量可能是一个合适的启发式方法，所以可以从得分高的大段开始。

回答于 2025-04-17 由 Python大师

分享举报

暴力破解的方法是使用递归。也就是说，对于每一个部分，我们会递归地找出使用这个部分能得到的最佳分数，以及不使用这个部分能得到的最佳分数。如果剩下的物品没有可能的组合，那么就给这个分数赋值为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

回答于 2025-04-17 由 Python大师

分享举报

为一组组合确定最高分

4 个回答

撰写回答