# Prove problem reduces to 0-1 knapsack problem

http://community.topcoder.com/stat?c=problem_statement&pm=12329

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):

1. play the first card and add Di to the total damage made and then discard it and the next Li - 1 cards
2. 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?

-

We can use induction to show that any set of cards can be picked as long as their levels do not add up to more than the number of cards. This is clearly true when we pick only $1$ card. Suppose this is true for $m-1$ cards. Now, let the indices of the $m$ cards to be picked be $i_1, i_2, \ldots , i_m$. As the levels add up to less than total number of cards, there must exist an $i_r$ such that $i_r + L_r \leq i_{r+1}$ (treat $i_{m+1}$ as $i_1 + n$, where $n$ is the total number of cards). Then place all cards above $i_r$ at the end of the list and discard $i_r$ first (note that this operation doesn't remove any other $i_k$ from the list). And by induction assumption, it follows that the remaining $m-1$ cards can be discarded too.