Разбиение массива на n равных по сумме |
Разбиение массива на n равных по сумме |
klem4 |
20.07.2010 15:15
Сообщение
#1
|
Perl. Just code it! Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
Необходимо разбить массив на N (2 в моем случае) равных по сумме массива. Есть 2 решения:
1 - перебором -- оптимально по результату, не оптимально по этическим соображениям 2 - следующий алгоритм: 1. сортируем начальный массив по убыванию. 1.1 A = [], B = []; 2. пока в начальном массиве есть элементы 2.1 ищем массив с мин. суммой из (A и B), кладем в него 0-й элемент из начального массива, удаляем его из начального массива. 2.2 goto 2 во втором варианте на начальном массиве [24,24,20,20,20], получаем A = [24,20], B = [24,20,20], неплохо, но не оптимально, оптимально будет A = [24,24], B = [20,20,20] Есть предложения ? -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
volvo |
20.07.2010 16:34
Сообщение
#2
|
Гость |
Есть... Вот такая, например, штуковина (на правах псевдокода):
procedure Tst is (будет работать, если только массив изначально отсортирован по убыванию) Вот чего выдает: 24 24 * 20 20 20 |
Lapp |
21.07.2010 8:22
Сообщение
#3
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Необходимо разбить массив на N (2 в моем случае) равных по сумме массива. Как я понял, все же не равных, просто нужно минимизировать разницу. Да?При N=2 - это чистейшая задача о рюкзаке (считаем полную сумму, делим на 2 и принимаем это за емкость рюка). При бОльших N, на самом деле, тоже, но поэтапно (делим сумму на N, набиваем первый рюк, остаток суммируем и делим на N-1 и т.д.) Конечно, перебор решает ее точно. Но похоже на то (судя по комментам), что тебя устроит некое "оптимальное" решение. Но тогда ты оговори условия этой оптимальности.. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
TarasBer |
21.07.2010 14:10
Сообщение
#4
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
Это АДА?
> (Every_Part - (Total + Numbers(i))) ** 2 > (Every_Part - Total) ** 2 А зачем квадрат, а не модуль? По смыслу же модуль явно - расстояние от среднего до текущей суммы. -------------------- |
Текстовая версия | 28.09.2024 23:58 |