Добрый день, коллеги, встала следующая задача.

Есть набор отрицательных чисел (до 1000 штук).

Например: start -2 -7 -45 -12 -11 -78 -9 end

Изначально находимся в точке start имеем права сдвигаться только на 1 или 2 шага (т.е. взять -2 или -7) и т.д. до самого конца. Необходимо взять из набора наибольшую сумму (или наименьшую по модулю). Чую, что задача на динамическое программирование, но общего решения придумать не могу.

Для этой задачи видимо лучшим будет:

start -> -7 -> -12 -> -11 -> -9 == -39

Искать решение "с конца" как делается в большинстве других задач динамического программирования, тоже не получается, вот пример:

 start -10 -4 -3 -7 -5 end

Идем с конца, по возможным шагам. Получаем end -> -5 -> -3 -> -4 -> start. Итого: -12.
А вариант end -> -7 -> -4  -> start, дает -11. 

Может кто узрел решение?

А в чём проблема... собсно тебе надо просчитывать стоимость попадания в каждый узел двумя способами, хранить соответственно результаты для трёх узлов, и ползти по списку. 

Вы уж меня простите, вот не понимаю.


Считать нужно с конца или не суть важно?


Для трех, это для текущего и двух его вариантов?

Это получается для списка из 10 элементов я буду хранить 2^10 вариантов? Или мы на каждом очередном шаге выбираем лучший результат, а остальные выкидываем?

Это сообщение отредактировал(а) becks - 24.9.2013, 17:05

важно или не важно. думаю не важно потому что 1000 чисел это четное количество и если будем суммировать в другой последовательности то конечная сумма не изменится.

а все.. наверно так. складываешь первое число со вторым, второе с третьим, первое с третьим и второе с четвертым. Получаешь 4 значения. Потом сравниваешь эти 4 числа выбираешь какое число больше подходит и двигаешься дальше.

Это сообщение отредактировал(а) миг - 24.9.2013, 20:12

1. посчитать наилучшую сумму, заканчивающуюся на первом числе
2. посчитать наилучшую сумму, заканчивающуюся на втором числе
3. посчитать наилучшую сумму, заканчивающуюся на третьем числе
и т.д.

естественно, запоминать уже посчитанное и использовать для следующих вычислений

Их может быть и нечетное число и не обязательно 1000. Точно до 1000.



Ну т.е. смотрим развитие событий на 4 шага вперед? почему на 4, а не на 3 или 5? Я не из какого-то злорадства, просто пытаюсь понять.



Тоже не очень понял, был бы благодарен за небольшой примерчик (буквально на 5-6 числах). Как в таком алгоритме учитывать возможность пропуска чисел?

Добавлено через 4 минуты и 18 секунд


Вот простой примерчик, где это не работает:
-1 -3 -5 -7 -9 -1

По вашему алгоритму идем : -1 -5 -7 -1 = -14
Оптимально: -3 -7 -1 = -11

Это сообщение отредактировал(а) becks - 24.9.2013, 21:37

maxim1000,  Похоже, что так.

Представим, что длина последовательности чисел - M и у нас уже есть оптимальное решение для чисел "от start до N" и "от start до {N+1}, причем эти решения используют конечную точку (n и n+1, соответственно). 

тогда, чтобы получить оптимальное решение для  n+2  достаточно перебрать варианты

решение(n)+{n+2}, решение(n+1)+{n+2}

Получим следующую пару решений для n+1 и n+2. Будем двигаться до точки M. В этой точке из пары значений выберем оптимальное. Оно и будет нужным нам решением.

Добавлено @ 21:54

n=1 - решение - 1
n=2 - решение - 3
n=3 - сравниваем -1-5 и -3-5 - решение -6
n=4 - сравниваем -6-7 и -3-7 - решение -10
n=5 - сравниваем -6-9 и -10-9 - решение -15
n=6 - сравниваем -15-1 и -10-1 - решение -11

выбираем минимум n6 и n5

Это сообщение отредактировал(а) ksnk - 24.9.2013, 21:56

ksnk,  maxim1000 все я понял. Большое спасибо всем за помощь. Очень благодарен.

  может и 5 решений просто алгоритм еще как следует не обдумал.

Добавлено @ 05:31
ksnk, прикольно, но не для всех случаев будет работать. например
start -2 -7 -45 -12 -11 -78 -9 end
1) сравниваем 2+45 и 7+45 - решение 47, но это не верное решение. т.к. есть более удачное решение 7+12=19. Поэтому 
нужно сравнить 2+7+45, 7+45, 7+12, 2+45, 2+7+12... решение будет 19...

Это сообщение отредактировал(а) миг - 25.9.2013, 05:40

миг, неправильно. В каждой точке есть 2 оптимальных решения от предыдущих шагов. Суммируем их со значением точки, выбираем  и получаем оптимальное для этой точки.
Для простоты, можно принять за 0 значения start и end, таким образом финальный шаг не нужно будет выделять в отдельное действие.

0(start) - 0 
1 - 2
2 - 0+7 и 2+7 выбираем 7
3 - 2+45 и 7+45 - выбираем 47
4 - 7+12 и 12+47 - выбираем 19
5 - 47+11 и 19+11  -выбираем 30
6 - 19+78 и 30+38 - выбираем 68
7 - 30+9 и 68+9 - выбираем 39
8(end) - 68+0 и 39+0  == 39

итого 7+12+11+9