----------------------------------- saltpro15 Wed Sep 30, 2009 3:29 pm 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 :D p.s. Sorry if this is in the wrong forum... general programming wouldn't let me add an attachment >.< ----------------------------------- A.J Wed Sep 30, 2009 9:20 pm RE:Dynamic Programming Problem ----------------------------------- Mr. Hughes has posed this problem to me about a year ago actually. A pretty straightforward problem. ----------------------------------- Cyril Wed Sep 30, 2009 10:36 pm 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 Thu Oct 01, 2009 8:50 am RE:Dynamic Programming Problem ----------------------------------- @Cyril- I thought he said that he didn't want us to post solutions here... ----------------------------------- saltpro15 Thu Oct 01, 2009 12:15 pm 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 Thu Oct 01, 2009 3:34 pm Re: RE:Dynamic Programming Problem ----------------------------------- 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 Thu Oct 01, 2009 7:02 pm RE:Dynamic Programming Problem ----------------------------------- Once again guys, isn't it against 'protocol' (:lol: 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 Thu Oct 01, 2009 7:03 pm 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 Thu Oct 01, 2009 10:02 pm 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 Thu Oct 01, 2009 10:31 pm Re: Dynamic Programming Problem ----------------------------------- 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 Sat Oct 03, 2009 12:16 am 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.