У меня есть список элементов, который выглядит примерно так:
[
["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
В настоящее время я решаю это путем прохождения упорядоченного списка зигзагообразным способом. Назначение предметов с большим весом в первом проходе каждой группе, придание элементам меньшего веса на втором проходе и т.д.
Это работает нормально, но у него есть недостатки. Я думаю, что второй проход по группам, в которых я обмениваюсь элементами между ними, приведет к более равномерно распределенным группам, но вовлеченный код может стать слишком сложным.
Знает ли кто-нибудь более эффективный или разумный способ сделать это?
Спасибо!