Minimizing Weight of a Linear Partition

Question

Let A[1:n] be a real array, and let k be an integer, 1 ≤ k ≤ n. A linear k-partition of A is a sequence of subarrays of the form [1:x1],[x1+1:x2],[x2+1:x3],…,[x(k-1)+1:n], for some x1< x2 <… < x(k−1).  That is, the array A got divided into k subarrays.  From this, we calculate the sums of each of k subarrays.  Finally, we take the maximum of those k sums, and that is defined as the weight of this linear k-partition.

Give an O(nk) dynamic programming algorithm to minimize the weight of the linear k-partition of the given array.

Answer 1

The most straight forward idea is going through all possible k partitions to find the minimum. However, the number of k partition of a array of size of N will be C(N-1, k), this is at least Ω(N^k).

Luckily, a dynamic programming is available as following:

1. Let S[i, j] represent the minimum weight of the linear j-partition of array[1: I]. What we are really interested in is S[N, k].

2. Optimality: The idea of the dynamic programming is "checking all possible partitions" as well, it has to lead to optimal result.

3. Base cases: when j = 1, then the partition of an array is itself, then the minimum of the 1-partition weight is just the sum of the total array from 1 to i. Thus, S[i, 1] =  sum(a[1: i]).

4. Let's build the recurrisive relation: Assume we have already calculated the minimum of 1~j partition weight of a[1: i]. Then the S[i, j + 1] would be the following: first divided the a[1: i] into two parts, then find the minimum of the weight of j-partition of the first part, and calculate the sum of the second part, compare and keep the larger one. The first part would have to be at least j elements and at most i - 1 elements. Go through all these possible "divides" and find the minimum of these results, which is just S[i, j + 1] by definition.

So the recurrisive formula would be: S[i, j + 1] = min_x_from_j_to_i-1{ max { S[x , j] , sum(a[x+1: i ]) }

The sum(a[x+1 : i] should be pre-calculated, so I use [] instead of ().

5. Time complexity analysis: Here, we have i = N, the value we need to calculate is size of k, for each value S[N, j], we need to do no more than 2*N comparations. So in total, the time complexity is O(Nk).

Pseudo code is simple so I'll skip this part.

Answer 2

Sadly, I still cannot come up with a DP approach, but I come up with a divide and conquer solution.  Since we divide the array into K partition so we can assume that the minimum weight cannot be smaller than the average of sums of each partition, that is to say the weight will always bigger than the Sum(A[1:n])/K. For convenience reason, we call this value as minPossibleWeight although we know it cannot be the weight. So my approach is to divide the K partitions into the left most partition and the rest K-1 partitions. Change the size of the left most partition from the 1 to the size its value exceeds the minPossibleWeight. And then try to compare its sum with the K-1 partitions' weight to see which is bigger. Then take the bigger one as the weight of the whole array. If this is the first time we do this we store the weight into a variable call the min, if this is not the first time then we compare the weight we get to the min to see which one is the smallest and we keep the smallest value to min. Things I haven't mentioned about is the right part K-1 partition. For this part we will recursively call our method to take it as a new array apply the same rules mentioned above to get its minimum weight.

Here is part of my code:

    public int getMinimumWeight(int array[],int start,int end, int k,int minPossibleWeight){

        if(k==1){  //base case 

            return this.sum(array, start, end);

        }

        int min=Integer.MAX_VALUE;

        int leftSum=0;

        for(int i=start;leftSum<minPossibleWeight;i++){

            leftSum+=array[i];

            int tmax=this.max(leftSum, this.getMinimumWeight(array, i+1, end, k-1,minPossibleWeight));

            if(tmax<min){

                min=tmax;

            }

        }

        return min;    

    }

    public int sum(int array[], int start,int end){

        int res=0;

        for(int i=start;i<=end;i++){

            res+=array[i];

        }

        return res;

    }

    public int max(int a,int b){

        return a>b ? a:b;

    }

Answer 3

To minimize the weight of the linear k-partition of the given array A[1:n], you can use dynamic programming. Define a 2D array DP where DP[i][j] represents the minimum weight of the linear j-partition for the subarray A[1:i]. The recurrence relation can be expressed as follows:

DP[i][j] = min{1 < x < i} { DP[x][j-1] + sum(A[x+1:i]) }]

Here, sum(A[x+1:i]) represents the sum of elements in the subarray A[x+1:i].

The base case is DP[i][1] = sum(A[1:i]) since the minimum weight of a linear 1-partition is the sum of the entire array.

The final answer will be in DP[n][k], as it represents the minimum weight of the linear k-partition for the entire array A.

                  DP[i][j] = min(DP[i][j], DP[x][j - 1] + prefix_sums[i] - prefix_sums[x])

 return DP[n][k]

code:

def linear_k_partition(A, k):

    n = len(A)

    prefix_sums = [0] * (n + 1)

    for i in range(1, n + 1):

        prefix_sums[i] = prefix_sums[i - 1] + A[i - 1]

    DP = [[float('inf')] * (k + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):

        DP[i][1] = prefix_sums[i]

 for j in range(2, k + 1):

        for i in range(1, n + 1):

            for x in range(i):

                DP[i][j] = min(DP[i][j], DP[x][j - 1] + prefix_sums[i] - prefix_sums[x])

  return DP[n][k]

A = [4, 8, 7, 6, 5, 1, 2, 3]

k = 3

result = linear_k_partition(A, k)

print(result)