将大小为N的集合拆分为M个组，这些组的和之间的差值最小

Question

有一组大小N

S = {n1, n2, n3, ..., nN}

我需要在M上拆分集合S

Groups = {{n1, n2}, {n3, n4, n5...},...,{... nN}} -> len(Groups) = M

两个相邻组之间的最大差值应尽可能小。差额的计算方法如下：

diff = abs(sum(G1) - sum(G2)) = abs((n1 + n2) - (n3 + n4 + n5))

我可以生成所有大小为N的向量，其中只包含M非零位数（如1），但我将不得不考虑50! / (25! * 25!)为错误的蛮力：（

例子：

6, 13, 10, 2
case 1: {6}, {13, 10, 2} -> difference = 25
case 2: {6, 13}, {10, 2} -> difference = 5
case 3: {6, 13, 10}, {2} -> difference = 29
The best case is second -> difference = 5!

我可以用什么方法来解决这个问题？




Answer 1

我通过结合动态规划和修改a*搜索解决了这个问题。

import heapq

def best_division (numbers, pieces):
    cumulative_sums = [0]
    for number in numbers:
        cumulative_sums.append(cumulative_sums[-1] + number)

    # We need this to be somewhat bigger than the maximum sum.
    # Making it + pieces/2 will result in a better
    # expected_piece_size.
    sum_bound = cumulative_sums[-1] + (pieces // 2)

    # We expect our pieces to be somewhere close to this size.
    expected_piece_size = (cumulative_sums[-1] + (pieces//2)) // pieces

    # This data structure will include:
    #
    #   By completed segments
    #       By start of segment
    #           By end of segment
    #               (lowest maximum difference, prev_start)
    #
    # It will actually be an array of dictionaries of dictionaries.
    #
    # It starts off empty.
    best_path_info = []

    # The queue is a minimum priority queue.
    #
    #   [
    #       lowest maximum difference,
    #       abs(sum of segment - expected_piece_size),
    #       count_pieces,
    #       start,
    #       end,
    #       prev_start
    #   ]
    #
    # This causes us to first look at the lowest maximum difference,
    # and then at the segment sum being close to the expected.
    #
    # It also means we can trace backwards once we have an answer.
    queue = []

    for i in range(len(cumulative_sums)):
        heapq.heappush(
            queue, [
                0,
                abs(cumulative_sums[i] - expected_piece_size),
                0,
                0,
                i,
                None
            ])

    while len(queue):
        max_diff, _, count_completed, start, end, prev_start = heapq.heappop(queue)
        if count_completed + 1 == pieces: # The current piece is not in the count
            if end == len(numbers):
                answer = [numbers[start:end]]
                end = start
                start = prev_start
                while start is not None:
                    answer.append(numbers[start:end])
                    count_completed -= 1
                    prev_start = best_path_info[count_completed][start][end][1]
                    end = start
                    start = prev_start
                ### RETURN HERE ###
                return list(reversed(answer))

            else:
                continue # Not a solution

        if len(best_path_info) <= count_completed:
            best_path_info.append({})

        path = best_path_info[count_completed]
        if start not in path:
            path[start] = {}
        path = path[start]
        if end not in path or max_diff < path[end][0]:
            path[end] = (max_diff, prev_start)
            for next_end in range(end, len(cumulative_sums)):
                this_sum = cumulative_sums[end] - cumulative_sums[start]
                next_sum = cumulative_sums[next_end] - cumulative_sums[end]
                next_max_diff = max(max_diff, abs(next_sum - this_sum))
                heapq.heappush(
                    queue, [
                        next_max_diff,
                        abs(next_sum - expected_piece_size),
                        count_completed + 1,
                        end,
                        next_end,
                        start
                    ])