@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=' ')
  • Вопрос задан
  • 402 просмотра
Пригласить эксперта
Ответы на вопрос 2
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Эвристическая оптимизация - по столбикам с положительными значениями надо прыгать подряд, как только впереди отрицательные значения - надо искать способ попасть на следующее положительное с минимальными потерями.
Таким образом задача разбивается на эквивалентные подзадачи меньшего объёма.
Решается поиском оптимального пути в ориентированном графе.
Ответ написан
Matmode
@Matmode
PHP/Symfony Developer
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)));
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы