CODEWITHSUNDEEP
pythonarrayspython-3.xalgorithmdynamic-programming
Jahid Chowdhury
Jahid Chowdhury

Reputation: 31

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

I wrote this code for splitting an array S into k continuous segments, to minimize the largest sum among these k segments. Here S is a sequence so I cannot change the ordering of the elements. Here is the code:

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)

This works perfectly well. But I would also like to return the segments for which I have calculated the min-max sum. For example, for the array S = [3,3,7,33] and k=3 this algorithm returns the answer '33' but I want to return the segments as [[3,3],[7],[33]]. But I am not being able to do it. Can anybody help me?

Upvotes: 1

Views: 751

Answers (1)

myrtlecat
myrtlecat

Reputation: 2276

You need to use a traceback technique (not sure if that name is widely used, or just in bioinformatics).

As you fill in your dynamic programming matrix with the best possible score for each sub-problem, you also fill in a traceback matrix that encodes the solution for each sub-problem.

For your problem, the traceback could store the optimal break-points for the sub-arrays:

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

Upvotes: 1

Related Questions