IPB
ЛогинПароль:

 
 Ответить  Открыть новую тему 
> Разбиение массива на n равных по сумме
сообщение
Сообщение #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";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






Есть... Вот такая, например, штуковина (на правах псевдокода):

procedure Tst is

type Array_Type is array(1 .. 5) of Integer;
Numbers: Array_Type := (24, 24, 20, 20, 20);

Partitions : constant Integer := 2; -- На сколько частей делить
Total, Every_Part : Integer := 0;
begin
for i in Numbers'Range loop
Total := Total + Numbers(i);
end loop;

Every_Part := Total / Partitions;
Total := 0;

for i in Numbers'Range loop

if (Every_Part - (Total + Numbers(i))) ** 2 > (Every_Part - Total) ** 2 then
Total := 0;
Put(" * "); -- В смысле, разделитель...
end if;

Put(" " & Integer'Image(Numbers(i)) & " ");
Total := Total + Numbers(i);
end loop;

end Tst;

(будет работать, если только массив изначально отсортирован по убыванию)

Вот чего выдает:
  24   24  *   20   20   20 
[2010-07-20 16:27:20] process terminated successfully (elapsed time: 00.12s)

 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(klem4 @ 20.07.2010 16:15) *
Необходимо разбить массив на N (2 в моем случае) равных по сумме массива.
Как я понял, все же не равных, просто нужно минимизировать разницу. Да?

При N=2 - это чистейшая задача о рюкзаке (считаем полную сумму, делим на 2 и принимаем это за емкость рюка). При бОльших N, на самом деле, тоже, но поэтапно (делим сумму на N, набиваем первый рюк, остаток суммируем и делим на N-1 и т.д.) Конечно, перебор решает ее точно. Но похоже на то (судя по комментам), что тебя устроит некое "оптимальное" решение. Но тогда ты оговори условия этой оптимальности.. smile.gif


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


Это АДА?

> (Every_Part - (Total + Numbers(i))) ** 2 > (Every_Part - Total) ** 2

А зачем квадрат, а не модуль? По смыслу же модуль явно - расстояние от среднего до текущей суммы.


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 12.12.2024 2:53
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name