Как разбить список предметов на равные разделы по весу предмета?
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:2810 плюса
25794 Репутация автора
Это оптимизационная версия проблемы разбиения , которая является NP-полной, хотя, согласно этой статье, «существуют эвристики, которые решают проблему во многих случаях, оптимально или приблизительно».
Раздел « Методы » этой статьи содержит несколько способов приблизительного или псевдополиномиального решения. В частности, если вы можете жить с приблизительным ответом, вы можете попробовать жадный подход:
Один из подходов к проблеме, имитирующий способ, которым дети выбирают команды для игры, - это жадный алгоритм, который просматривает числа в порядке убывания, присваивая каждому из них любое подмножество с меньшей суммой.
Время выполнения этого подхода составляет O(n^2)и гарантирует, что вы получите результат в пределах 4/3 от точного решения.
Если у вас должно быть точное решение, а ваш набор данных достаточно мал, вы всегда можете использовать метод грубой силы, генерирующий каждую возможность (это экспоненциально O(2^n)). В зависимости от ваших требований к производительности, этого может быть достаточно.
-3 плюса
78 Репутация автора
Вопросы из категории :
- algorithm Функция для создания цветовых колес
- algorithm Big O, как вы рассчитываете / приближаете это?
- algorithm Пиковое обнаружение измеренного сигнала
- algorithm Головоломка: Найти самый большой прямоугольник (проблема максимального прямоугольника)
- algorithm Объединить Сортировать связанный список
- algorithm Алгоритм нахождения наибольшего простого множителя числа
- algorithm Алгоритм сравнения двух изображений
- algorithm Как я могу измерить сходство между двумя изображениями?
- algorithm Рассчитать расстояние между двумя точками широты и долготы? (Формула Haversine)
- algorithm Как обнаружить дубликаты данных?
- split Как разбить строку, чтобы я мог получить доступ к элементу x?
- split Как я могу токенизировать строку в C ++?
- split Есть ли в Python функция для разбиения слова на список?
- split Разделение разделенной точкой с запятой строки в словаре в Python
- split How do I split a string with any whitespace chars as delimiters?
- split Как разбить список на куски одинакового размера?
- split Регулярное выражение для разбиения строки с использованием пробела, когда оно не заключено в одинарные или двойные кавычки
- split Разделение строки на слова и пунктуацию
- split Разделить строку Java на новую строку
- split Разделенная строка Java на куски по 1024 байта