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

Question

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

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

Answer 1

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

Answer 2

Назовем ваши «y суммы» бункеров. Вы заявляете, что хотите распределить свои предметы в сбалансированном состоянии между всеми ящиками.

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

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

Answer 3

Я бы, вероятно, сделал это с 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 4

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