Divide array into k parts so as to Minimize the maximum partition sum

Question

An array has been provided with a size n. We have to divide this array into k consecutive blocks such that the maximum of the sum of each block comes out to be minimum. We have to return this value.

For eg: [5, 10, 30, 20, 15] can be partitioned as 5 10 | 30 | 20 15 to give the maximum partition sum as max(15, 30, 35) = 35 which is the minimum in this case hence the code should return 35.

This SO question is similar: How to partition an array of integers in a way that minimizes the maximum of the sum of each partition?

I did implement this approach. However, I found out that if the number of sets that can be formed is greater than k for a particular selection, it is not necessary that exactly k partitions are attainable as two partitions might not be able to merge.

For eg [5, 10, 30, 20, 15], and k=3 If we consider wanting a sum of 30 for a partition, 5 10 | 30 | 20 | 15 i.e. 4 sets can be made. Yet we cannot have exactly 3 sets from the same hence making the solution wrong.

My Code:

int minimizeParition(vector<int> arr, int k)
{
    int totalSum = 0;
    for(int i=0; i<arr.size(); i++) totalSum += arr[i];

    int low = 0, high=totalSum, mid;
    int result;
    while(low<=high)
    {
        cout << low << " " << high << endl;
        mid = (low + high) / 2;
        int sets = 0, curSum = 0, i;
        for(i=0; i<arr.size(); i++) {
            if(arr[i]>mid) break;
            else if(curSum+arr[i] > mid) {
                curSum = arr[i];
                sets++;
            } else curSum += arr[i];
        }
        if(i==arr.size()) sets++;
        if(sets <= k) {
            result = mid;
            high = mid-1;
        } else low = mid+1;
    }
    return result;
}

In your first example, if you swap 5 and 15 the max is 30. Why should it return 35? — Nelewout, Jul 24 '21 at 08:35
You cannot swap elements. You have to properly partition these elements so as to get the desired result. @N.Wouda — Aman Kukretti, Jul 28 '21 at 03:59
Why can I not swap them? I propose 15 10 | 30 | 20 5, which differs from your partition by swapping 15 and 5 between the first and third subsets of the partition. — Nelewout, Jul 28 '21 at 07:03
@N.Wouda : We cannot swap them because the question mentions so!! When making partitions, we cannot rearrange the array in any way so as to have a better answer. The problem is to minimize the maximum partition sum attained for k partitions. If we could swap them, we would just sort them and pair i and n-i for each value! So that would have been a relatively easy question. — Aman Kukretti, Jul 28 '21 at 09:55
I have updated your question to clarify this. The question did *not* mention this: it stated "k parts". There was nothing about those parts being consecutive blocks. — Nelewout, Jul 28 '21 at 10:44

Divide array into k parts so as to Minimize the maximum partition sum

0 Answers0