The Partition Problem is a very old conundrum in computer science. The usual question goes: given some buckets of some capacity, and some items of some size, how can I distribute the items by the buckets in an optimal manner?
The answer to this is more complex than it seems at first glance, as it depends on what you mean by some buckets and by optimal.
- Do you know in advance how many buckets you have? Or their size?
- Do you have to fill more buckets with fewer items or less buckets with more items?
- Do you allow bucket overflow or enforce capacity?
- Do you want the perfect distribution regardless of performance or is fast-and-furious good enough for you?
There are lots of ways of answering these questions and even more ways of implementing solutions for them, from simple greedy algorithms to more complex heuristics based ones.
Today I’ll get you started the basics for a simple and generic distribution algorithm based on a descending greedy approach, with a couple of variations: