Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Dynamic Programming Problem
Index -> C++
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
saltpro15




PostPosted: Wed Sep 30, 2009 3:29 pm   Post subject: Dynamic Programming Problem

Hey all,

So my CS teacher gave me an idea for a knapsack DP problem, and I put a bit of a twist on it (Can't make things too easy now!). Here it is in .odt and .pdf form. Please don't post solutions here, as it rather ruins it for other people, but you are welcome to discuss it Very Happy




p.s.

Sorry if this is in the wrong forum... general programming wouldn't let me add an attachment >.<



DP.odt
 Description:

Download
 Filename:  DP.odt
 Filesize:  14.03 KB
 Downloaded:  483 Time(s)


DP.pdf
 Description:

Download
 Filename:  DP.pdf
 Filesize:  49.08 KB
 Downloaded:  575 Time(s)

Sponsor
Sponsor
Sponsor
sponsor
A.J




PostPosted: Wed Sep 30, 2009 9:20 pm   Post subject: RE:Dynamic Programming Problem

Mr. Hughes has posed this problem to me about a year ago actually. A pretty straightforward problem.
Cyril




PostPosted: Wed Sep 30, 2009 10:36 pm   Post subject: RE:Dynamic Programming Problem

Since there are only 19 different ages, take the top 4 of each age, and use brute force. 76 choose 4 is very small. You should probably change some bounds...
A.J




PostPosted: Thu Oct 01, 2009 8:50 am   Post subject: RE:Dynamic Programming Problem

@Cyril- I thought he said that he didn't want us to post solutions here...
saltpro15




PostPosted: Thu Oct 01, 2009 12:15 pm   Post subject: RE:Dynamic Programming Problem

Brute forcing would be O(N^2) complexity right? With N = 5000, that probably won't run in a second. An O(N*M) DP algorithm is still needed. I'll make a giant test case though to make sure the brute forcing solutions will fail
bbi5291




PostPosted: Thu Oct 01, 2009 3:34 pm   Post subject: Re: RE:Dynamic Programming Problem

saltpro15 @ Thu Oct 01, 2009 12:15 pm wrote:
Brute forcing would be O(N^2) complexity right? With N = 5000, that probably won't run in a second.

No, I think 25 million operations in a second is reasonable on a fast computer. Depends on what they are, of course.
A.J




PostPosted: Thu Oct 01, 2009 7:02 pm   Post subject: RE:Dynamic Programming Problem

Once again guys, isn't it against 'protocol' (Laughing had to use that word) to post possible solutions here?

And Drew, the DP solution isn't all that bad. And, once again, ask Mr.Hughes if it is possible for you guys to make a trip here (as we can't make it there due to lack of a CS teacher at our school, and lack of funding).
saltpro15




PostPosted: Thu Oct 01, 2009 7:03 pm   Post subject: RE:Dynamic Programming Problem

AJ, I'll PM you what I've done so far tomorrow, as the code is saved on my school account. I have this basically done
md




PostPosted: Thu Oct 01, 2009 10:02 pm   Post subject: RE:Dynamic Programming Problem

Moved to a more appropriate forum.

I don't think discussing posibilities or directions at a solution is the same as posting an actual solution. Though 25 million posibilities is quite a bit - brute force might work but definitely not the way to go.
bbi5291




PostPosted: Thu Oct 01, 2009 10:31 pm   Post subject: Re: Dynamic Programming Problem

md wrote:

Moved to a more appropriate forum.

I think this thread should go in General Programming. It really doesn't have anything to do with C++ in particular.
Cyril




PostPosted: Sat Oct 03, 2009 12:16 am   Post subject: RE:Dynamic Programming Problem

Well, I don't think it's inappropriate to post solutions that have nothing to do with the title of the thread. Since we're not posting the intended algorithms, I think it counts as discussion, rather than giving away the DP solution.
Display posts from previous:   
   Index -> C++
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 11 Posts ]
Jump to:   


Style:  
Search: