列表元素的公平分区

Question

给定一个球员评分列表，我需要尽可能公平地将球员（即评分）分成两组。目标是最小化团队累积评分之间的差异。我如何将球员分成几队没有限制（一支球队可以有 2 名球员，另一支球队可以有 10 名球员）。

例如：[5, 6, 2, 10, 2, 3, 4]应该返回([6, 5, 3, 2], [10, 4, 2])

我想知道解决这个问题的算法。请注意，我正在参加在线编程入门课程，因此将不胜感激简单的算法。

我正在使用以下代码，但由于某种原因，在线代码检查器说它不正确。

def partition(ratings):
    set1 = []
    set2 =[]
    sum_1 = 0
    sum_2 = 0
    for n in sorted(ratings, reverse=True):
        if sum_1 < sum_2:
            set1.append(n)
            sum_1 = sum_1 + n
        else:
            set2.append(n)
            sum_2 = sum_2 + n
    return(set1, set2)

更新：我联系了导师，被告知我应该在函数中定义另一个“帮助”函数来检查所有不同的组合，然后我需要检查最小差异。

Answer 1

因为我知道我必须生成所有可能的列表，所以我需要创建一个“辅助”函数来帮助生成所有可能性。完成此操作后，我确实检查了最小差异，并且具有该最小差异的列表的组合就是所需的解决方案。

辅助函数是递归的，并检查列表组合的所有可能性。

def partition(ratings):

    def helper(ratings, left, right, aux_list, current_index):
        if current_index >= len(ratings):
            aux_list.append((left, right))
            return

        first = ratings[current_index]
        helper(ratings, left + [first], right, aux_list, current_index + 1)
        helper(ratings, left, right + [first], aux_list, current_index + 1)

    #l contains all possible sublists
    l = []
    helper(ratings, [], [], l, 0)
    set1 = []
    set2 = []
    #set mindiff to a large number
    mindiff = 1000
    for sets in l:
        diff = abs(sum(sets[0]) - sum(sets[1]))
        if diff < mindiff:
            mindiff = diff
            set1 = sets[0]
            set2 = sets[1]
    return (set1, set2)

示例： r = [1, 2, 2, 3, 5, 4, 2, 4, 5, 5, 2]，最佳划分为：([1, 2, 2, 3, 5, 4], [2, 4, 5, 5, 2])差异为1。

r = [73, 7, 44, 21, 43, 42, 92, 88, 82, 70]，最优划分为：([73, 7, 21, 92, 88], [44, 43, 42, 82, 70])差异为0.