Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
Dynamic Programming Problem
Author Message
saltpro15

Posted: 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

p.s.

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

DP.odt
Description:
Filename:  DP.odt
Filesize:  14.03 KB

DP.pdf
Description:
Filename:  DP.pdf
Filesize:  49.08 KB

A.J

Posted: 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

Posted: 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

Posted: 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

Posted: 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

Posted: 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

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

Once again guys, isn't it against 'protocol' ( 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

Posted: 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

Posted: 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

Posted: 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

Posted: 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: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 11 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: