I was practicing on TopCoder and found this problem. I solved it by noticing that it looks a little like the 0-1 knapsack, but I do not have even the smallest clue why this assumption was correct.
I will simplify the problem statement here:
Given a ordered list of cards, each with a level and a damage, you can make the following steps in order to maximize your damage (assuming the first card has level Li and damage Di):
- play the first card and add Di to the total damage made and then discard it and the next Li - 1 cards
- move the first card to the end of the list (so the second card becomes the first, the third becomes second, etc)
My question is: can you always play any cards you want as long as you don't have to discard more cards than they actually are? Can you reduce this to the 0-1 knapsack problem where you can choose any items to put in the backpack as long as you do not exceed the maximum weight?