How can I improve my algorithm for finding optimally balanced P-way partitioning of array
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, https://cs.stackexchange.com/questions/82479/optimal-partition-of-book-chapters, https://cs.stackexchange.com/questions/38330/a-partition-algorithm, https://cs.stackexchange.com/questions/89663/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. 690
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. 864