Задачка про минимизацию последовательности натуральных чисел

Автор темы mdi 
ОбъявленияПоследний пост
ОбъявлениеПравила и принципы форума «Высшая математика»28.10.2009 15:17
ОбъявлениеПремия для молодых математиков Образовательного фонда «Талант и успех»21.06.2021 00:48
ОбъявлениеЧисло «Пи» рассчитано с рекордной точностью на «бюджетном» компьютере27.08.2021 22:26
15.04.2003 13:58
mdi
Задачка про минимизацию последовательности натуральных чисел
олимпиада по программированию, задачка такая:

есть последовательность натур. чисел
надо расставить знаки "+" или "-" перед ее членами таким образом,
чтобы модуль суммы членов новой последовательности был минимальным.

какие идеи?
15.04.2003 14:16
e-Past
какие ограничения?
Размер последовательности / время ожидания ответа
15.04.2003 14:23
e-Past
например
Можно применить алгоритм построения оптимально сбалансированного бинарного дерева, рассматривая сами числа в качестве весов. Потом перед всеми чисел, расположенных на одной ветви от корня дерева, ставишь знак "-", на другой - "+".
15.04.2003 14:25
e-Past
наверняка можно проще и быстрее
т.к. сбалансированность дерева требуется только в корневом узле, сбалансированность всех прочих узлов не имеет значения.
15.04.2003 14:57
mdi
постойте,постойте...
что значит "рассматривая сами числа в качестве весов" ?
15.04.2003 15:39
e-Past
то и означает :-О
Ну например:
Пусть у нас есть 4 числа: 4, 2, 1, 1.
Тогда построенное оптимально сбалансированное дерево будет таким:
(8)
4 (4)
2 (2)
1 1
В скобочках помечены веса узлов, составленных объединением двух других. В данном случае разница в весе будет 0 - вес левой ветви от корня, содержащей единственное исходное число 4, равен весу правой ветви, в которую вошли все остальные числа.
15.04.2003 15:49
Necr
Эта задача
Эта задачка довольно известна. Считается, что она NP-полна.
15.04.2003 16:45
Елена
Алгоритм
Попробуй исходя из этого алгоритма (это язык MATLAB)
% -- form acquisition
ru = rand(1,1000)*1000;
nru = floor(ru)+1;
% -- sort it
snru = sort(nru);
isnru = snru(1000:-1:1);
% -- algorithm of minimization
s = isnru(1);
for i=2:1000
sp = s+isnru(i);
sn = s-isnru(i);
if (abs(sp)<abs(sn))
s = sp;
else
s = sn;
end;
end;
15.04.2003 17:45
e-Past
похоже, неправильно
Например, возьмем такой массив:

15 9 4 4 4 4 4 4

Ваш алгоритм даст решение

15-9-4-4+4-4+4-4+4 = 2

Правильный ответ:
15+9-4-4-4-4-4-4 = 0
15.04.2003 17:49
e-Past
ошибся
Извиняюсь, лишнюю четверку дописал в конце - конечно, должно быть
15-9-4-4+4-4+4-4 = -2

Но суть проблемы от этого не меняется. :-)
15.04.2003 20:07
DP
Если члены последовательности разумно малы, то подойдет динамическое программирование. Время работы составит O(VN^2), где
N -- длина последовательности, а V - ограничение на члены.
16.04.2003 08:48
Елена
Субопт. реш.
Это NP-полная задача и для нахождения оптимального решения необходимо перебрать все множество, варьируя знаки. Я предложила субоптимальное решение.
16.04.2003 10:54
mdi
на конкурсе
интересно, разумно ли давать такую задачку на конкурсе, проставив разбалловку в зависимости от значений получающихся сумм?
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти