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

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

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

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

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

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

Спасибо!

Ответы

Ответ 1

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

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

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

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

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

Ответ 2

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

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

Ответ 3

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