Grouping Items into Balanced Groups

Question

What's the best way to group x amount of items into y amount of groups based on a variable property of each item eg. weight.

Leaving me with y amount of groups each holding the same sum(price) (or close to the same). So the groups are balanced by cumulative weight.

Answer 1

Use java.util.Arrays.sort(Object[] a, Comparator c) with an implementation of Comparator that sorts according to your requirements.

Answer 2

Let's call your "y amounts" bins. You state that you want to distribute your items into balanced between all bins.

One structure that has a similar property is balanced trees. What I'd do, then, is the following. First, populate a balanced tree using the chosen property as a key. Next, descend into a desired level of the tree, such that there are N elements on that level, N being the amount of bins you want. Put all element descendent from each of those nodes into a separate bin.

The only thing left, then, is distributing the elements on the nodes above that level into the bins. Just chose a criteria for selecting to what bin it will go and apply that. Your bins should be reasonably balanced.

Answer 3

I'd probably do that with a Map of Sets indexed by the property. Something like:

Map<K, Set<V>> results = new HashMap<K, Set<V>>();
for (V item : items) {
    K key = item.getProperty();
    Set<V> group = results.get(key);
    if (group == null) {
        group = new HashSet<V>();
        results.put(key, group);
    }
    group.add(item);
}

Where V is the type of your items and K the type of the property.

Answer 4

This is Partition problem generalized to y groups instead of 2. The problem for y=2 is weakly NP-hard, so there exists a pseudopolynomial algorithm that solves it effectively, as long as the weights are small integers.