1
$\begingroup$

I have an array of $N$ weights $w_i$, say $w_i=\{4, 5, 12, 16, 3, 10, 1\}$, and I need to divide this array into $P$ partitions such that partitions are optimally balanced, i.e. that maximum sum of weights of any partition is as small as possible. Luckily the problem is constrained by the fact that the weights can't be reordered. If the number of partitions is three, the above example would give the optimal partitions: $\{4, 5, 12\}, \{16\}, \{3, 10, 1\}$.

I have found efficient recipes (e.g. partition problem, subset sum, Optimal Partition of Book Chapters, A partition algorithm, An algorithm for k-way array partitioning) for many similar problems for the cases where the weights are unordered sets and/or the number of partitions is fixed at 2 or 3, but none that seem to exactly address my problem where the number of partitions is arbitrary.

I have solved the problem myself using divide-and-conquer algorithm (written in Python below), but it seems to be awfully slow for many partitions (e.g. N=100, P=8). So I was thinking that there got to be a better way, using dynamic programming or some other clever tricks?

Does anyone have any suggestions?

Slow Python divide-and-conquer algorithm:

def findOptimalPartitions(weights, num_partitions):
    if num_partitions == 1:
        # If there is only one partition, it must start at the first index
        # and have a size equal to the sum of all weights.
        return numpy.array([0], dtype=int), sum(weights)

    # Initially we let all partitions start at zero, meaning that all but the
    # last partition gets zero elements, and the last gets them all.
    partition_offsets = numpy.array([0] * num_partitions)
    max_partition_size = sum(weights)

    # We now divide the weigths into two partitions that split at index n.
    # We know that each partition should have at least one element, so there
    # is no point in looping over all elements.
    for n in range(1, len(weights) - num_partitions):
        first_partition_size = sum(weights[:n])

        if first_partition_size > max_partition_size:
            # If the first partition size is larger than the best currently
            # found, there is no point in searching further.
            break

        # The second partition that starts at n we now further split into
        # subpartitions in a recursive manner.
        subpartition_offsets, best_subpartition_size = \
            findOptimalPartitions(weights[n:], num_partitions - 1)

        # If the maximum size of any of the current partitions is smaller
        # than the current best partitioning, we update the best partitions.
        if ((first_partition_size < max_partition_size)
                and (best_subpartition_size < max_partition_size)):
            # The first partition always start at 0. The others start at
            # ones from the subpartition relative to the current index, so
            # add the current index to those.
            partition_offsets[1:] = n + subpartition_offsets
            # Find the maximum partition size.
            max_partition_size = max(first_partition_size, best_subpartition_size)

    return partition_offsets, max_partition_size

EDIT: A trivial Greedy algorithm where the last partition will typically be too large.

def greedyPartition(weights, num_partitions):
    target_size = sum(weights) / num_partitions

    partition_offsets = numpy.zeros(num_partitions, dtype=int)
    partition_sizes = numpy.zeros(num_partitions, dtype=int)
    current_divider = 0
    for p in range(0, num_partitions - 1):
        partition_size = 0
        for n in range(current_divider, len(weights)):
            if partition_size + weights[n] > target_size:
                current_divider = n
                partition_offsets[p + 1] = current_divider
                partition_sizes[p] = partition_size
                break

            partition_size += weights[n]
    partition_sizes[-1] = sum(weights) - sum(partition_sizes[:-1])
    max_partition_size = max(partition_sizes)

    return partition_offsets, max_partition_size
$\endgroup$
5
  • 1
    $\begingroup$ Notice, that instead of finding the smallest maximal part, you can look for a number $W$ such that you can split array into parts with weights not larger then $W$. For given $W$ you can use it greedy algorithm. Now to find minimal $W$ notice that if there is partition with weights not larger then $W$ then also exists a partition with weights not larger then $W+1$ $\endgroup$ May 16 '20 at 22:49
  • $\begingroup$ Start with a balanced partition: let target weight be sum of weights divided by number of partitions. Accumulating, when exceeding the current target, check whether sum before or after current element was closer. Adjust target value. $\endgroup$
    – greybeard
    May 17 '20 at 5:10
  • $\begingroup$ @SzymonStankiewicz, I've made a Greedy algorithm that will simply create partitions not exceeding a target which is set to the average partition weight, and whatever is left is assigned to the last partition. This has the downside that the last partition can become quite a bit larger than the optimal. How do you suggest to improve this? Should I iterate the algorithm increasing the target or...? I'm not sure I quite understand your comments correctly, so maybe you can elaborate? (I've updated my question with the greedy algorithm) $\endgroup$
    – Filip A
    May 17 '20 at 17:39
  • $\begingroup$ @FilipA Are all weight positive? $\endgroup$
    – John L.
    May 17 '20 at 18:56
  • $\begingroup$ It looks like my answer just expounds @Szymon's comment. $\endgroup$
    – John L.
    May 18 '20 at 0:58
0
$\begingroup$

Binary search is a general strategy that can often be applied to problems that seeks a single optimized number as an answer.


Let $A=[a_1, \cdots, a_N]$ be the given array of weights. Assume $1\lt P\lt N$; otherwise, the problem becomes trivial.

Given a weight $w$ such that $1\le w\le\sum a_i$, we can associate a partition $\mathcal P(w)$, $A = P_1\,P_2\,\cdots P_m$ such that

  1. Subarray $P_1$ is as long as possible such that the sum of all weights in it is no more than $w$.
  2. Then subarray $P_2$ is as long as possible such that the sum of all weights in it is no more than $w$.
  3. Then subarray $P_3$ is as long as possible such that the sum of all weights in it is no more than $w$.
  4. And so on.
  5. Finally, we are left with non-empty subarray $P_m$, the sum of all weights in which is no more than $w$.

Note that $m=\#\mathcal P(w)$ is the minimum number of subarrays in a partition where the sum of all weights in every subarray is at most $w$. We want to find $w$ such that $\#\mathcal P(w)=P$ and $\#\mathcal P(w+1)<P$. Since the map from $w$ to $\mathcal P(w)$ is decreasing, we can use binary search to find it.

Here is the outline of an algorithm that finds the largest $w$ such that $\mathcal P(w)=P$. Assume the given weights are integers; otherwise, we need to tweak the algorithm a bit. .

  1. Let $ma=\max\{a_i\}$. If $P\ge \#\mathcal P(ma)$, the least maximum sum is $ma$. Deal with this easy case and return.

  2. Let $low=ma$ and $high=\sum a_i$.

  3. If $low\lt high-1$, $ mid = (low + high)//2$ and compute $m= \#\mathcal P(mid)$.

    • If $m\le P$, lower $high$ to $mid$.
    • If $m\gt P$, raise $low$ to $mid$.

    Go back to the start of this step.

  4. Let $H$ be the partition $\mathcal P(high)$. If $\#H\not= P$, divide some subarrays of $H$ into smaller subarrays so as to increase the number of subarrays by $P-\#(P)$. Return $H$.

The loop invariant for step 3 is $\#\mathcal P(low)>P$, $\#\mathcal P(high)\le P$ and $low\le high-1$. When the loop ends, i.e., when $low==high-1$, we must still have $\#\mathcal P(low)>P$ and $\#\mathcal P(high)\le P$. That means, $high$ is the minimum of the maximum sum of weights of any subarray in a partition of size no more than $P$, which explains largely why this algorithm is correct.


This algorithm runs in $O(N\log(\sum a_i))$ time, since the most of time is spent on computing $\mathcal P(w)$ and it takes $O(N)$ time to compute $\mathcal P(w)$ for any given weight $w$.


Exercise (the dual problem). Given an array of $N$ positive integer weights $w_i$ and an integer $P$, divide the array into $P$ parts such that the parts are optimally balanced, i.e. that minimum sum of weights of any part is as large as possible.

$\endgroup$
2
  • $\begingroup$ Thanks for the elaborate response. I did make a variation of Szymons suggestion that would iterate the Greedy algorithm and it works ok, but I'm not sure it guarantees the optimal solution. I'll try out the binary search version when I find time this week and accept your answer when I have a working implementation (I see no reason why it shouldn't work). $\endgroup$
    – Filip A
    May 18 '20 at 16:39
  • $\begingroup$ Here is my code at replt.it. For N = 100000, P=100, weights randomly selected between 1 and 1000000, it takes a fraction of a second to compute. $\endgroup$
    – John L.
    May 19 '20 at 1:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.