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 >.<
Description: 

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

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






Sponsor Sponsor



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






Sponsor Sponsor



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.






