Search code examples
pythonalgorithmoptimizationlanguage-agnosticcombinatorics

splitting list in chunks of balanced weight


I need an algorithm to split a list of values into such chunks, that sum of values in every chunk is (approximately) equals (its some variation of Knapsack problem, I suppose)

So, for example [1, 2, 1, 4, 10, 3, 8] => [[8, 2], [10], [1, 3, 1, 4]]

Chunks of equal lengths are preferred, but it's not a constraint.

Python is preferred language, but others are welcome as well

Edit: number of chunks is defined


Solution

  • Greedy:
    1. Order the available items descending.
    2. Create N empty groups
    3. Start adding the items one at a time into the group that has the smallest sum in it.

    I think in most real life situations this should be enough.