1
ビデオゲームでは、Nレベルがあり、そのレベルに勝つためにはそれぞれに一定のエネルギー量が必要です。あなたはレベル0で0エネルギーでゲームを開始し、レベルに勝つたびにレベルに必要なエネルギーを消費します（あなたのエネルギーは0以下にならない）。また、各レベルには、コストCでエネルギー量Eを販売する店舗が0,1、またはそれ以上あります。レベルを超えるために十分なエネルギーがなければ、他の店から購入することはできません。あなたが店から購入するたびに、あなたの新しいエネルギー量はE（店が売るもの）です。つまり、あなたの以前のエネルギーを合計しません。この最適化はどのように解決されますか？
質問：すべてのNレベルに勝つために必要な最低限の金額は？ （お金は無限で、あなたが望むすべてのお店を買うことができると仮定しますが、必要なものだけを購入するように最適化します）
私はこの問題に対する解決方法を知りたいと考えています。この種の問題を解決する問題解決テクニックはありますか？もしそうなら、あなたは説明できますか？私が最初に勉強しなければならない同様の既知の問題はありますか？
重複している状態を見つけて動的プログラミングを使用することを望んで、再帰的なバックトラッキングを試みましたが、見つけられませんでした。私の州：すべてのお店について、2つの支店をフォークします...ショップを買うか、しません。
これは8クイーンの問題と似ていますが、これはバックトラック深度の最初の検索を使用して解決されましたが、すでに試したようです。同じレベルの複数のショップから購入すると、エネルギーが足りないため、私には何の利益ももたらさないので、私は各店舗で買い物をしません。私は良いアイデアは、あなたがレベルで立ち往生し、バックトラックし、より高いエネルギーを購入する場合は、次のレベルにジャンプすることができます最小エネルギーを購入することだと思う。 –