Числа?

← →
Йцукен (2004-01-28 21:00) [0]

Даны числа, необходимо из них составить 2-а массива, таких чтобы разность сумм, между массивами была миниально.
Как это можно сделать, объясните пожалуйста!

← →
TUser (2004-01-28 21:17) [1]

> разность сумм, между массивами

вот это - поподробнее, plz ...

← →
Йцукен (2004-01-28 21:36) [2]

Разность сумм между массивами,т.е. "сумма всех элементов 1-ого массива - сумму всех элементов 2ого массива = минисум"
Как это можно сделать? Объясните? Как это все перебрать?

← →
jack128 (2004-01-28 22:30) [3]

первое число помещаешь в массив А. Далее помещаешь числа в массив В пока сумма В не станет больше А. Далее помещаешь числа в массив А пока сумма А не станет больше В. И так в цикле пока не кончатся числа.

← →
Йцукен (2004-01-29 13:52) [4]

{1005}
var n,i:byte;
a,b,t:longint;
begin
assign(input,"input.in");
reset(input);
a:=0;
b:=0;
read(n);
read(a);
for i:=1 to n-1 do
begin
if a>b then
begin
read(t);
b:=b+t;
end
else
begin
read(t);
a:=a+t;
end;
end;
writeln(abs(b-a));
end.
Правильно? (нужно найи только разницу сумм)

← →
ghg (2004-01-29 14:35) [5]

массивы по длине как должны соотноситься (равны или могут отличаться)?

← →
MBo (2004-01-29 14:40) [6]

Ну элементарная логика-то должна же работать....
Если из набора чисел нужно составить два набора с наиболее близкими суммами, то какая сумма должна быть примерно в каждом массиве?

← →
pasha_golub (2004-01-29 14:47) [7]

MBo © (29.01.04 14:40) [6]
Наверно максимально близкая к половине общей суммы?

← →
MBo (2004-01-29 14:50) [8]

>pasha_golub
ОК, вот ты не зря в школе учился ;)

а дальше задача о рюкзаке - переборная - выбрать из набора такие числа, чтобы отклонение их суммs от половинки было минимальным.

← →
SergP (2004-01-29 14:55) [9]

> jack128 © (28.01.04 22:30) [3]
> первое число помещаешь в массив А. Далее помещаешь числа
> в массив В пока сумма В не станет больше А. Далее помещаешь
> числа в массив А пока сумма А не станет больше В. И так
> в цикле пока не кончатся числа.

В таком случае не мешало бы исходный массив отсортировать и начать раскидывать с чисел которые больше..
Хотя и это ИМХО не всегда даст правильный результат...

← →
MBo (2004-01-29 14:59) [10]

>начать раскидывать с чисел которые больше..
Это разумно
>Хотя и это ИМХО не всегда даст правильный результат...
Все равно эта задача требует перебора, например, методом ветвей и границ, и гарантировать лучшее решение можно только перепробовав все варианты или остановившись при нахождении нулевой разницы.

← →
ghg (2004-01-29 15:11) [11]

а теперь ко всему этому еще добавить условие равенства массивов :)

← →
TUser (2004-01-29 15:53) [12]

> ghg © (29.01.04 15:11) [11]

Еще проще. Сортируем чила. Считаем разности, сортируем разности. Берем 2 числа с минимаьной разностью между ними. Пихаем их в разные массивы. То же самое проделываем со всеми остальными числами. Время работы - зависит от способа сортировки, но скажем так - n*log(n).

← →
Vit@ly (2004-01-29 15:58) [13]

В общем-то далеко не очевидно, что это будет наилучший результат, хотя и оригинально

Числа? Найти похожие ветки