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

Question

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

[
  ["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

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

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

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

Спасибо!

Answer 1

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

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

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

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

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

Answer 2

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

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

Answer 3

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