Question

Can someone post a link to a good thread to PS8 number 4? I imagine this has been covered in this forum but I can't seem to find it. Thanks in advance.

Answer 1

I think I found this link in another forum: kudos to Proficiamus

http://proficiamus.blogspot.com/

Answer 2

Just for the record, my output matched his for subjects.txt with 20 hours max work.

Answer 3

http://curiousreef.com/class/mit-opencourseware-600-introduction/
This site has lots of posted solutions to all the problem sets.
I found 8.4 to be harder than all the other problems on all the other problem sets, combined. It's a real PITA, but it's rewarding to finally complete it. You need to understand, at a very deep level, exactly what the recursive algorithm is doing, what exactly is being stored in the memo, how the list of subjects is updated for each recursive call (and updated again when the recursive call exits), and what is being returned from the recursive function.

When I was debugging with print statements, I found I wanted to know the path of skip/take branches that got me to where I was, but that wasn't easily determinable. I added a "path" string parameter to the recursive function, started it with an empty string, and for each skip call appended an "s" to it, and for each take call appended a "t". I found that to be extremely useful. It won't immediately reveal the secrets of the universe, but it is one handy little tool to use while investigating the algorithm.

Answer 4

you can start by trying to adapt the findMaxVal function shown in one of the lectures - it mimics, pretty well, the decision tree shown in the lecture for the knapsack problem - the adaptation will be that you have to preserve the items taken

put something like this at the bottom of your module and you can have a couple of small dictionaries to test with
http://dpaste.com/627592/

when you work it out, please post it - i like to see different solutions to this one

Answer 5

I had way too much fun with this particular problem. The brute force method was taking minutes to complete with a mere 10-hour selection, so I was pleasantly surprised when my dynamic programming exercise did the 168-hour in 0.04 seconds. My status line on the output was:

168 Hour analysis took 0.04 seconds, 297500 recursions, and had 102056 memo hits.

Have a look if you like. I'll be checking out the other programs on this thread to see what other approaches were tried.

http://codepad.org/FIohsPdx