0-1 Knapsack Problem in Spoj

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.

1 Like

@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 :smiley:

(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

Code With MAX_N = 5

Hope this helps :slight_smile:

1 Like

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.