Ordered open-end knapsack problem optimised for minimum weight range

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?

• What's the context where you encountered this problem? If you ran across it somewhere, can you credit the source? As far as how to solve it, see cs.stackexchange.com/tags/dynamic-programming/info for the general method.
– D.W.
Jan 26, 2023 at 6:12
• Thanks for your comment @D.W. and for the pointer to dynamic programming, I will take a look. The context is that I'm trying to create a Bible reading plan to read through a book of the Bible in a given number of days. So the containers are days and the items are chapters, e.g. reading the book of Psalms in January there are 31 days and 150 chapters. The chapters range widely in length from Psalm 117 (31 words) to Psalm 119 (2,472 words) and I want the daily word count to vary as little as possible. Hence the need to preserve item order and optimise for the minimum weight range. Jan 26, 2023 at 14:28

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.

• Brilliant, thanks very much! I'll have a go at that and come back to you to accept your answer. Jan 27, 2023 at 6:46
• I'm trying to implement this in Python but I don't completely follow the notation in your recursive relation. Specifically the meaning of $i_0$ and $W[i_0 + 1]$. Could you possibly give me an example of building the algorithm with trivial inputs of e.g. 2 containers and the items [1, 2, 3]? Feb 2, 2023 at 21:49
• @matkins, $i_0$ ranges over all values $i_0:=1,2,\dots,i-1$ such that $W[i_0+1]+\dots + W[I] \ge \ell$. The min is taken over all of the values you obtain by iterating over those values of $i_0$.
– D.W.
Feb 3, 2023 at 0:53