将给定数组拆分为 K 个具有最小-最大总和的段

Question

我编写了这段代码，用于将数组 S 分成 k 个连续的段，以最小化这 k 个段中的最大总和。这里 S 是一个序列，所以我无法更改元素的顺序。这是代码：

def Opt(i, j):
    n = len(i)
    sum = [0]*(n+1)
    dp = [[0 for a in range(n+1)] for a in range(2)]
    for a in range(0,n):
        sum[a+1] = i[a] + sum[a]
        dp[0][a+1] = float('inf')
        dp[1][a+1] = float('inf')
    for a in range(1,j+1):
        for b in range(1,n+1):
            for c in range(a-1,b):
                dp[a%2][b] = min(dp[a%2][b], max(dp[(a-1)%2][c], sum[b]-sum[c]))
    return dp[j%2][n]

# Driver Code
if __name__ == '__main__':
    S = [7,2,5,10,8]
    k = 2
    M = sum(S)/len(S)
    ans = Opt(S,k)
    print(ans)

这非常有效。但我也想 return 我计算了最小-最大总和的部分。例如，对于数组 S = [3,3,7,33] 和 k=3，此算法 return 的答案是“33”，但我想 return 将段设为 [[3,3],[7],[33]]。但我做不到。有人可以帮助我吗？

Answer 1

您需要使用 traceback 技术（不确定该名称是否被广泛使用，或者仅在生物信息学中使用）。

当您用每个 sub-problem 的最佳分数填充动态规划矩阵时，您还填充了一个对 [=17= 进行编码的回溯矩阵每个 sub-problem.

的解决方案

对于您的问题，回溯可以存储 sub-arrays 的最佳 break-points:

def Opt(i, j):
    n = len(i)
    sum = [0]*(n+1)
    dp = [[0 for a in range(n+1)] for a in range(2)]
    tb = [[[] for a in range(n+1)] for a in range(2)]

    for a in range(0,n):
        sum[a+1] = i[a] + sum[a]
        dp[0][a+1] = float('inf')
        dp[1][a+1] = float('inf')

    for a in range(1,j+1):
        for b in range(a + 1,n+1):
            for c in range(a - 1, b):
                # if c should be a breakpoint, then...
                if max(dp[(a-1)%2][c], sum[b]-sum[c]) < dp[a%2][b]:
                    # ...update the best score, and...
                    dp[a%2][b] = max(dp[(a-1)%2][c], sum[b]-sum[c])
                    # ...update the solution
                    tb[a%2][b] = tb[(a - 1)%2][c] + [c]

    # extract optimal sub-arrays
    starts = tb[j%2][n]
    ends = starts[1:] + [n]
    sub_arrays = [i[s:e] for s, e in zip(starts, ends)]

    return sub_arrays


S = [7,2,5,10,8]

Opt(S, 2)              # ==> [[7, 2, 5], [10, 8]]
Opt(S, 3)              # ==> [[7, 2, 5], [10], [8]]
Opt([3, 7, 7, 33], 3)  # ==> [[3, 7], [7], [33]]

将给定数组拆分为 K 个具有最小-最大总和的段

Split the given array into K segments with Min-max sum

python

arrays

algorithm

dynamic-programming

python-3.x