В видеоигре есть N уровней, каждый из которых требует, чтобы у вас было определенное количество энергии, чтобы выиграть этот уровень. Вы начинаете игру на уровне 0 с 0 энергией, и каждый раз, когда вы выигрываете уровень, вы тратите энергию, требуемую уровнем (ваша энергия не может опускаться ниже 0). Также на каждом уровне есть 0, 1 или более магазинов, которые продают количество энергии E по цене C. Если вы обнаружите, что вам не хватает энергии, чтобы пройти уровень, вы теряете, потому что вы не можете перейти на предыдущие уровни, чтобы покупать в других магазинах. Всякий раз, когда вы покупаете в магазине, ваше новое количество энергии E (тот, который продается в магазине), то есть он не суммируется с вашей предыдущей энергией.Как решить эту оптимизацию?
Вопрос: Каковы минимальные деньги, необходимые для того, чтобы выиграть все уровни N? (при условии, что деньги бесконечны, и вы можете купить все магазины, которые хотите, ... но я хочу оптимизировать его так, чтобы он покупал только необходимые)
Мне интересно узнать, как найти решение для этого. Есть ли какой-либо метод решения проблем, который решает такие проблемы, если да, можете ли вы объяснить ?. Есть ли аналогичные известные проблемы, которые я должен изучить в первую очередь?
Я пробовал использовать рекурсивный backtracking, надеясь найти перекрывающиеся состояния и использовать динамическое программирование, но я их не нашел. Мои штаты, где: для всех магазинов, вилка двух ветвей ... покупает магазин, или нет.
Это похоже на структуру проблемы с четырьмя королями, и это решение решается с использованием глубины поиска по глубине первого поиска, но похоже, что вы уже пробовали его. Я не буду входить в каждый магазин (покупать или не покупать), потому что покупка из нескольких магазинов на том же уровне не дает мне никакой пользы, поскольку энергия не суммируется. Я думаю, что хорошей идеей было бы купить минимальную энергию, которая позволит вам перейти на следующий уровень, если в любой момент вы застряли на уровне, отступите назад и купите более высокую энергию. –