Группировка товаров в сбалансированные группы

Question

Каков наилучший способ сгруппировать количество элементов x в количество групп y на основе переменного свойства каждого элемента, например. вес.

Оставляя меня с y количеством групп, каждая из которых содержит одинаковую сумму (цену) (или близкую к одной и той же). Таким образом, группы сбалансированы по совокупному весу.

Answer 1

Я бы, вероятно, сделал это с Map из Set s, проиндексированными свойством. Что-то вроде:

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);
}

Где V - тип ваших предметов, а K - тип имущества.

Answer 2

Используйте java.util.Arrays.sort(Object[] a, Comparator c) с реализацией Comparator, которая сортирует в соответствии с вашими требованиями.

Answer 3

Это Проблема разбиения обобщена на y группы вместо 2. Задача для y=2 слабо NP-сложна, поэтому существует псевдополиномиальный алгоритм, который эффективно ее решает, пока веса - это маленькие целые числа.

Answer 4

Давайте назовем ваши "у суммы" бункеров . Вы заявляете, что хотите распределить свои предметы в сбалансированном виде по всем лоткам.

Одна структура, которая имеет подобное свойство, это сбалансированные деревья. То, что я буду делать, это следующее. Сначала заполните сбалансированное дерево, используя выбранное свойство в качестве ключа. Затем спуститесь на нужный уровень дерева, чтобы на этом уровне было N элементов, а N - это количество бинов, которое вы хотите. Поместите все потомки элементов от каждого из этих узлов в отдельную корзину.

Осталось только распределить элементы в узлах выше этого уровня в контейнеры. Просто выберите критерий для выбора того, в какое хранилище он пойдет, и примените его. Ваши контейнеры должны быть разумно сбалансированы.