I tried 0-1 Knapsack in Spoj using top down dp but got WA. Please help me what is the wrong in my code. My code :

@raschedcs your solution is correct, just change the value of MAX_N to 2010 and it will get AC.

LINK to your AC solution after changing the value of MAX_N.

@rashedcs Your solution is correct just change MAX_N to 2001 New Code

**EDIT:** In the problem description it is written, **… S (1 <= S <= 2000). You also have N (1<= N <= 2000) …** But in the program you have declared `memo[MAX_N][MAX_N]`

where MAX_N = 2000 (Original Program).

Now if they give N, S = 2000, then `memo[2000][2000]`

is used but in the function `int knapSack(int n, int w)`

you have used `memo[n][w]`

everywhere which means `memo[2000][2000]`

but you can only access till `memo[1999][1999]`

as index starts from 0!

In short, your program was giving out some gibberish value (when N=2000) due to index error which was leading to WA! That’s why changing MAX_N to 2001 leads to AC

(Extra info - Suppose you used MAX-N = 5. According to you, your program should be able to give correct output when **N, S <= 5** but it outputs some gibberish value when running on the example taken from SPOJ

Hope this helps

Please tell me - But why change size 2001?

Please tell me - But why change the value of MAX_N?

As memo[2000][2000] will give garbage value with MAX_N = 2000 when N or S = 2000. See my edited answer for details.