Взять из набора отрицательных наибольшую сумму

 
0
 
Algorithms
ava
becks | 24.09.2013, 15:59
Добрый день, коллеги, встала следующая задача.

Есть набор отрицательных чисел (до 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.

Может кто узрел решение?
Comments (9)
ava
Akina | 24.09.2013, 15:22 #
А в чём проблема... собсно тебе надо просчитывать стоимость попадания в каждый узел двумя способами, хранить соответственно результаты для трёх узлов, и ползти по списку. 
ava
becks | 24.09.2013, 17:03 #
Цитата


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



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

Цитата


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


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

Цитата


хранить соответственно результаты для трёх узлов, и ползти по списку


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

Это получается для списка из 10 элементов я буду хранить 2^10 вариантов? Или мы на каждом очередном шаге выбираем лучший результат, а остальные выкидываем?
ava
миг | 24.09.2013, 19:52 #
Цитата (becks @  24.9.2013,  17:03 findReferencedText)
Считать нужно с конца или не суть важно?

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

Цитата (becks @  24.9.2013,  17:03 findReferencedText)
Или мы на каждом очередном шаге выбираем лучший результат, а остальные выкидываем?

может Akina, имел ввиду следующее: берешь три первых числа сравниваешь их модули и одно число выкидываешь. наверно максимальное число по модулю выкидываешь (если я правильно понял условие). а два мелких числа складываешь. ну и двигаешься так дальше до конца.
ava
maxim1000 | 24.09.2013, 20:57 #
1. посчитать наилучшую сумму, заканчивающуюся на первом числе
2. посчитать наилучшую сумму, заканчивающуюся на втором числе
3. посчитать наилучшую сумму, заканчивающуюся на третьем числе
и т.д.

естественно, запоминать уже посчитанное и использовать для следующих вычислений
ava
becks | 24.09.2013, 21:36 #
Цитата


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


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

Цитата


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



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

Цитата


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

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

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

и т.д.



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



Тоже не очень понял, был бы благодарен за небольшой примерчик (буквально на 5-6 числах). Как в таком алгоритме учитывать возможность пропуска чисел? 
ava
ksnk | 24.09.2013, 21:45 #
maxim1000,  Похоже, что так.

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

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

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

Получим следующую пару решений для n+1 и n+2. Будем двигаться до точки M-1. В этой точке из пары значений выберем оптимальное. Оно и будет нужным нам решением.
ava
becks | 24.09.2013, 21:58 #
ksnk,  maxim1000 все я понял. Большое спасибо всем за помощь. Очень благодарен.
ava
миг | 25.09.2013, 05:19 #
Цитата (becks @  24.9.2013,  21:36 findReferencedText)
Ну т.е. смотрим развитие событий на 4 шага вперед? почему на 4, а не на 3 или 5? Я не из какого-то злорадства, просто пытаюсь понять.

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

start -2 -7 -45 -12 -11 -78 -9 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
Please register or login to write.
Firm of day
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Contributors
  maxim1000   Akina   ksnk   миг   becks
advanced
Submit