Balanced weight distribution into buckets, but with a twist (aka sharding a list into k even shards)

Question

Is there an existing algorithm that can solve the following problem?

Problem

Given an list N comprised of integers of various values, shard the list into k buckets such that:

1. The sum of the integers in each bucket are roughly evenly divided (as much as possible
2. Only consecutive integers are placed in the same bucket

Example:

Given k (the number of buckets) = 4

List N = [4 1 2 6 19 1 10 3 2 2]

A Valid Solution

[4 1 2] [6] [19] [1 10 3 2 2]

(Since the bucket weights add up to 7, 6, 19, 18)

An Invalid Solution

[1 1 2 2 2 3] [1 4 6] [10] [19]

(Where the bucket weights would add up to 11, 11, 10, 19)

It's invalid because the buckets no longer contain only numbers that were adjacent in the original list.

Thanks!

Answer 1

Yes, this can be solved as a straightforward application of dynamic programming, once you define an objective function to measure how "evenly divided" the buckets are. Let $A[j]$ denote the value of the objective function for the best way to split integers 1..j. Then you can compute the value of $A[j]$ given the values of $A[1],\dots,A[j-1]$ (you just consider all possibilities for how many integers go in the last bucket), so there is a dynamic programming algorithm with running time at most $O(n^2)$.

This problem is sometimes called the Linear Partition Problem, and a solution can be found in Section 8.5 of Skiena's "Algorithm Design Manual".