Как разбить список предметов на равные разделы по весу предмета?

algorithm split

7806 просмотра

3 ответа

1104 Репутация автора

У меня есть список предметов, который выглядит примерно так:

[
  ["orange", 9],
  ["watermelon", 3],
  ["grapefruit", 6],
  ["peach", 8],
  ["durian", 2],
  ["apricot", 6]
]

Я хотел бы разделить этот список на ... скажем, две группы так, чтобы сумма весов предметов в каждой группе была как можно более равной, то есть:

List 1:
  orange: 9
  durian: 2
  apricot: 6
  TOTAL: 17

List 2:
  watermelon: 3
  grapefruit: 6
  peach: 8
  TOTAL: 17

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

Это работает хорошо, но у него есть недостатки. Я думаю, что второй проход по группам, в которых я обмениваюсь элементами между ними, приведет к более равномерно распределенным группам, но соответствующий код может стать слишком сложным.

Кто-нибудь знает более эффективный или умный способ сделать это?

Спасибо!

Автор: Federico Cáceres Источник Размещён: 08.09.2010 08:10

Ответы (3)


1 плюс

9037 Репутация автора

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

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

Автор: Beth Размещён: 08.09.2010 08:28

10 плюса

25794 Репутация автора

Решение

Это оптимизационная версия проблемы разбиения , которая является NP-полной, хотя, согласно этой статье, «существуют эвристики, которые решают проблему во многих случаях, оптимально или приблизительно».

Раздел « Методы » этой статьи содержит несколько способов приблизительного или псевдополиномиального решения. В частности, если вы можете жить с приблизительным ответом, вы можете попробовать жадный подход:

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

Время выполнения этого подхода составляет O(n^2)и гарантирует, что вы получите результат в пределах 4/3 от точного решения.

Если у вас должно быть точное решение, а ваш набор данных достаточно мал, вы всегда можете использовать метод грубой силы, генерирующий каждую возможность (это экспоненциально O(2^n)). В зависимости от ваших требований к производительности, этого может быть достаточно.

Автор: Chris Schmich Размещён: 08.09.2010 08:34

-3 плюса

78 Репутация автора

Это не сработает. Например, S = {5, 5, 4, 3, 3}.

Автор: andreych Размещён: 05.02.2014 10:47
Вопросы из категории :
32x32