×

# 0-1 Knapsack Problem in Spoj

 0 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 : http://ideone.com/LNzSgj asked 25 Dec '16, 12:44 2★rashedcs 497●6●17●55 accept rate: 4%

 2 @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. answered 25 Dec '16, 13:34 5★srd091 1.6k●1●11 accept rate: 42% Please tell me - But why change the value of MAX_N? (26 Dec '16, 01:11) rashedcs2★
 2 @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 :D (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 :) answered 25 Dec '16, 13:42 371●2 accept rate: 23% Please tell me - But why change size 2001? (26 Dec '16, 01:11) rashedcs2★ As memo[2000][2000] will give garbage value with MAX_N = 2000 when N or S = 2000. See my edited answer for details. (26 Dec '16, 01:29)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,212

question asked: 25 Dec '16, 12:44

question was seen: 746 times

last updated: 26 Dec '16, 01:58