Ordered open-end knapsack problem optimised for minimum weight range

Question

Given a fixed number of infinite-capacity containers and a list of items of varying weights, how can I best place the items into the containers preserving their original order in a way that minimises the difference between the heaviest and lightest containers?

For example, given 3 containers and 10 items with weights [19, 7, 12, 1, 9, 11, 3, 17, 10, 8] the optimal solution is:

1. 19, 7
2. 12, 1, 9, 11, 3
3. 17, 10, 8

Such that the difference between the heaviest and lightest containers is (12 + 1 + 9 + 11 + 3) - (19 + 7) = 10.

My current algorithm is to:

• calculate the target bin weight as the sum of all item weights divided by the number of containers
• if adding the next item to the active container would bring its weight closer to the target then add it to the active container
• otherwise move to the next container and add the item
• repeat until all items have been placed in containers

This algorithm works well for lists of items of similar weights but doesn't find the best solution when there are one or more very heavy items.

For example, with 4 containers and item weights [3, 8, 2, 4, 8, 2, 27, 20] the above algorithm gives:

• 3, 8, 2, 4
• 8, 2
• 27
• 20

With a weight range of 27 - (8 + 2) = 17.

However the optimal solution is in fact:

• 3, 8, 2
• 4, 8, 2
• 27
• 20

With a weight range of 27 - (3 + 8 + 2) = 14.

How can I find the optimal solution?

Answer 1

This can be solved with dynamic programming. Let $W[1,\dots,n]$ denote the weights of the items. Fix a value of $\ell$. Define the array $A[\cdot,\cdot]$ as

$A[i,j] = $ the smallest value of $h$ such that there is an allocation of the first $i$ items to the first $j$ containers where the lightest container is $\ge \ell$ and the heaviest container is $\le h$

We have the recursive relation:

$$A[i,j] = \min\{\max(A[i_0,j-1],W[i_0+1]+\dots+W[i]) \mid W[i_0+1]+\dots+W[i] \ge \ell\}$$

This can be used to build a dynamic programming algorithm, which fills in entries of $A[i,j]$ in order of increasing $j$. Then $A[n,m]-\ell$ contains the smallest possible difference between heaviest and lightest containers, assuming the lightest container is $\ell$. Finally, we can repeat this algorithm once per value of $\ell$ (for each $\ell$ in the range $1,2,3,\dots,(W[1]+\dots+W[n])/m)$).

The overall running time will be $O(n^2 S)$, where $S=W[1]+\dots+W[n]$ is the sum of the weights. This might be fast enough if the sum of the weights is not too large. If the sum of weights is very large, you might need a different approach.