Какой алгоритм для решения задачи на динамическое программирование про лестницу и монеты?

Question

[kolomiec_artiom]

Добрый день! Пытаюсь реализовать алгоритм для задачи:

Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до N . В начале Кузнечик сидит на столбике с номером 1. Он может прыгнуть вперед на расстояние от 1 до K столбиков, считая от текущего.

На каждом столбике Кузнечик может получить или потерять несколько золотых монет (для каждого столбика это число известно). Определите, как нужно прыгать Кузнечику, чтобы собрать наибольшее количество золотых монет. Учитывайте, что Кузнечик не может прыгать назад.

Но сталкиваюсь с тем, что алгоритм работает слишком медленно и не совсем корректно. Хотелось бы узнать, как можно оптимизировать код и в каком месте программы я допускаю ошибку, из-за которой алгоритм работает не совсем корректно:

#coding=utf8

n, k = map(int, (input().split()))

stolb = list(map(int, (input().split())))

# Добавляем на 1 и последние ступени нули, т.к они без монет 
stolb.insert(0, 0)
stolb.append(0)
max_step = []

# Список с макс.кол-вом монет и список с ходами
max_money = [0]
best_step = []

for i in range(1, len(stolb)):
    i_prev_bs = i - 1
    tmp = max_money[i_prev_bs]
    for j in range(max(0, i-k), i):
        if max_money[j] > tmp:
            i_prev_bs = j
            tmp = max_money[i_prev_bs]
        
    max_money.append(tmp + stolb[i])
    best_step.append(i_prev_bs + 1)

best_step.append(n)
best_step = set(best_step)
    
print(max_money[-1])
print(len(best_step) -1)
for tmp in best_step:
    print(tmp, end=' ')

Comments

[Роман]

Очень глупая постановка задачи!

Просто перепрыгивая столбики с отрицательным количеством монет он наберет максимум.

По моему в условии должно быть что то про ограничение количества ходов.

[kolomiec_artiom]

Роман, ну, хорошо. Решите по вашему алгоритму следующее:
K = 1
N = 5: 0, -10, -10, -10, 0

Он просто не сможет перепрыгнуть все отрицательные столбцы

[Роман]

kolomiec_artiom, при данной постановке он вообще не имеет выбора и всегда прыгает на 1

[Роман]

kolomiec_artiom, а вообще, погуглите такое: "нахождение оптимального пути по графам"
Можно найти много примеров, в том числе и программных реализаций.

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

[Вадим]

kolomiec_artiom вы уверены, что во втором цикле он должен идти до i? Есть подозрения что там должно быть i-1. Вообще, алгоритм ваш верен (попадать в вершину t из последней из k вершин с найбольшей суммой), но я не уверен, что в худшем случае его как-то удастся оптимизировать

[Вадим]

Добавлю - ваш внешний цикл при i=1 всегда добавит первое значение в стек best_steps, что неверно. Пример
K=3
-5, - 100, - 300, - 5000, 100000

Оптимально прыгнуть на - 100, а потом 100000.

[Евгений]

Здесь идеально «ляжет» алгоритм Дейкстры.

https://m.habr.com/ru/post/111361/

Answer 1

[Rsa97]

Эвристическая оптимизация - по столбикам с положительными значениями надо прыгать подряд, как только впереди отрицательные значения - надо искать способ попасть на следующее положительное с минимальными потерями.
Таким образом задача разбивается на эквивалентные подзадачи меньшего объёма.
Решается поиском оптимального пути в ориентированном графе.

Answer 2

[Вадим]

kolomiec_artiom Добавляя к своим комментариям, позволил себе написать алгоритм. Он схож с вашим, но есть некоторые отличия о которых я писал в комментариях.

Вывод алгоритма (данные внутри кода)

php solution.php
Steps: 1 2 4 6 9
Values: 10 20 30 -100 100000

Сам алгоритм:

<?php

$k = 3;
$weight = [1 => 10, 20, -5, 30, -5, -100, -3000, -5000, 100000];
$n = count($weight);

$sum = [];
$comeFrom = [];

$sum[0] = 0;
$comeFrom[0] = 0;

for ($i = 1; $i <= $n; $i++) {
    $comeFromIndex = $i - 1;
    for ($j = max(0, $i - $k); $j <= ($i - 1); $j++) {
        if ($sum[$j] > $sum[$comeFromIndex]) {
            $comeFromIndex = $j;
        }
    }

    $sum[$i] = $sum[$comeFromIndex] + $weight[$i];
    $comeFrom[$i] = $comeFromIndex;
}

$steps = [];
while ($n) {
    $steps[] = $n;
    $n = $comeFrom[$n];
}

echo 'Steps: ' . implode(' ', array_reverse($steps));
echo "\n";
echo 'Values: ' . implode(' ', array_intersect_key($weight, array_combine($steps, $steps)));