Необходимо разбить массив на 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]
Есть предложения ?
Есть... Вот такая, например, штуковина (на правах псевдокода):
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)
Это АДА?
> (Every_Part - (Total + Numbers(i))) ** 2 > (Every_Part - Total) ** 2
А зачем квадрат, а не модуль? По смыслу же модуль явно - расстояние от среднего до текущей суммы.