Dynamic Programming Problem

[saltpro15]

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

[A.J]

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

[Cyril]

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]

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

[saltpro15]

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]

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]

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]

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]

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]

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]

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.