задача динамического программирования, поиск оптимальных посещений магазинов

Question

Скажем, у нас есть список магазинов, в которых при посещении содержится какое-то значение.Например, store_value = [2,4,9,1,4,2].

Запуск из магазина в магазин для сбора значения имеет определенную стоимость, например, run_cost = [0,1,2,3,1,2].То есть, если я бегу, чтобы собрать значение 9 в магазине i = 3 (не проиндексировано 0), оно будет стоить 2, что означает, что я не смог бы посетить 2 предыдущих магазина из-за требуемой стоимости.Считайте, что это количество отдохнувшего перед запуском в магазин.

Теперь, используя динамическое программирование, мы могли бы сказать V (x, i), где V (0, i) - максимальное значение, которое можно получить после первого сохранения i, если мы НЕ запускаем для сохранения i.V (1, i) - это максимальное значение, которое можно получить после первого сохранения i, если мы действительно запустим сохранение i.

Что бы P (0, i) и P (1, i) выполнялись из хранилища i= 1..6 похоже?

Я попытался запустить алгоритм, но что-то подсказывает мне, что я делаю что-то не так.Из того, что я мог бы собрать:

P (0,1) = 0, P (1,1) = 2

, отсюда я считаю, что я неправ: P (0,2) = 2, P (1,2) = 4 ... и т. Д.

Если бы кто-то мог помочь мне понять, как я должен думать об этой проблеме, я был бы признателенмного.

Answer 1

Более простой формулировкой было бы определить V(i) как максимальное значение, которое может быть достигнуто с магазинами 1..i.Тогда рекурсивное определение:

V(i) = max(
           V(i - 1),                                //do not visit store i
           store_value[i] + V(i - run_cost[i] - 1)  //visit store i
       )

Необходимо соблюдать осторожность, когда run_cost равно 0.