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.