1
비디오 게임에는 N 레벨이 있으며, 각 레벨은 해당 레벨에서 이기기 위해 일정량의 에너지가 필요합니다. 0 레벨의 에너지로 레벨 0에서 게임을 시작하고 레벨을 획득 할 때마다 레벨에서 요구하는 에너지를 소비합니다 (에너지가 0 미만이 될 수 없음). 또한 각 레벨에는 비용 C로 에너지 양 E를 판매하는 0 개, 1 개 또는 그 이상의 상점이 있습니다. 레벨을 통과 할만큼 충분한 에너지가 없다면 다른 상점에서 구매할 수없는 이전 레벨로 이동할 수 없으므로 손실됩니다. 상점에서 구입할 때마다 새로운 에너지 양은 E (상점에서 판매하는 것)입니다. 즉, 이전 에너지까지 합산하지 않습니다.이 최적화를 어떻게 해결합니까?
질문 : N 레벨을 모두 얻는 데 필요한 최소 금액은 얼마입니까? (돈이 무한하다고 가정하고 원하는 모든 상점을 구입할 수는 있지만 ... 필요한 경우에만 구입할 수 있도록 최적화하고 싶습니다.)
나는이 문제를 어떻게 해결할 수 있는지 알고 싶습니다. 이런 종류의 문제를 해결하는 문제 해결 기법이 있습니까? 그렇다면 설명해주십시오. 내가 먼저 공부해야하는 유사한 문제가 있습니까?
중복 된 상태를 찾고 동적 프로그래밍을 사용하여 재귀 적으로 역 추적을 시도했지만 찾지 못했습니다. 내 주 어디에서 : 모든 상점에 대해 두 개의 분기를 포크로 ... 상점을 사거나 그렇지 않습니다.
이것은 8 개 퀸즈 문제와 구조가 비슷하며 심도 깊은 첫 번째 검색을 사용하여 해결되었지만 이미 시도한 것처럼 보입니다. 같은 수준의 여러 매장에서 구매하면 에너지가 합산되지 않으므로 어떤 이점도 얻지 못하기 때문에 모든 상점 (구매 또는 구매하지 않음)으로 분기하지 않습니다. 나는 좋은 생각이 당신이 다음 단계로 뛰어 넘을 수있는 최소 에너지를 구입하는 것이라고 생각합니다. 어느 시점 에라도 당신이 한 수준에 머물러 있다면 역행하고 더 높은 에너지를 구입하십시오. –