You are not logged in. Please login at www.codechef.com to post your questions!

×

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 : http://ideone.com/LNzSgj

asked 25 Dec '16, 12:44

rashedcs's gravatar image

2★rashedcs
49761755
accept rate: 4%


@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.

link

answered 25 Dec '16, 13:34

srd091's gravatar image

5★srd091
1.6k111
accept rate: 42%

edited 25 Dec '16, 13:35

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

(26 Dec '16, 01:11) rashedcs2★

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

link

answered 25 Dec '16, 13:42

nikhil_chandak's gravatar image

5★nikhil_chandak
3712
accept rate: 23%

edited 26 Dec '16, 01:58

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) nikhil_chandak5★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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