Question

any advice on implementing the dynamic programming solution to pset 8 recursively using a decision tree? while easy to maximise, i'm stumped on keeping track of the included subjects...

Answer 1

Something that helped me out a lot was when someone told me I could create another helper function which dpAdvisor will call which does the actual dynamic tree.

This dpHelper can take in arguments (index, maxWork, course names, course dictionary) and return (value, best registration dictionary ). Hope that gives you some inspiration

Answer 2

I've had some luck towards solving my problem, by making a memo that maps tuple of (number of subjects, avail. work) to a list of [value, [indices of selected subjects]].
However, my recursive algorithm still does not appear as efficient as the iterative implementation using a matrix table...
http://dpaste.com/hold/612186/

Answer 3

i found that the matrix/table method was about ten times faster than the solution i wrote that uses a recursive algorithm that mimics the decision tree - i didn't try to figure out why but i have a feeling that the matrix/table method is doing less work.

Answer 4

i'm not sure either, but the recursive algorithm may work more effectively for problems where the possible 'weights' are less continuous....

Answer 5

bwCA, could you post some example code of a matrix/table method? I'm badly stumped on this one and would like to see how that works.

Answer 6

tombedor, I haven't gotten this far in the exercises, but I read about matrices. For information about lists as matrices, see section 8.15 in:
http://www.greenteapress.com/thinkpython/thinkCSpy/html/chap08.html

and to see dictionaries as matrices, see section 10.4 in:
http://www.greenteapress.com/thinkpython/thinkCSpy/html/chap10.html

Answer 7

I'm having the same problem as the original post, and my code is very similar. I mapped it directly to the knapsack problem code from the lecture. The code loops back on itself so much that I can't tell where to put in calls to grab the selected classes and add them to the solution dictionary.

I've printed out just about every line in the code, and I can see all the compares. It seems you need to keep two dictionaries that are updating as the program tries the "with" and "without" branches, but so far I've been unable to get a dictionary that contains the right classes. Does that sound right? Can anyone suggest how to change podzol's posted code to do that?

Answer 8

gcarter80, i think you could either alter the memo (see my earlier post) or, i guess but not tried, have the recursive function return a tuple of a memo value and a set of included items.
you modify the set of included subjects if with_i > without_i, preserve it if without_i > with_i, but you also initiate it for the basecase scenarios.

Answer 9

Thanks podzol, that appears to be the direction you have to go. I noted in another ps8 thread that I found this thread online where a bunch of people posted their answers to this problem - http://curiousreef.com/class/mit-opencourseware-600-introduction/lesson/14/retricen/1/

Answer 10

so here is a file with both algorithms.

dpAdvisor, dpAdvisorHelper and
the matrix/table algorithm which is in these functions:
yutoobAdvisor, makeArrays, and makewinnerlist

there is a lot of xtra testing stuff in there and lots of comments, hope it isn't too confusing.

Answer 11

The first thing I did was make a short list of subjects to search (7 items). The call stack will get as deep as the number of subjects, so you've got to shorten that up right away to make testing manageable. Also, you can manually look through 7 subjects to figure out the right answers.

You need a helper function to be the recursive function.

The recursive call tree makes it hard to know exactly where you are in the tree when debugging, so I added a "path" string to the recursive function. In lecture he called the two recursive calls "skip" and "take," so when I took the "skip" branch I appended an "s" to path, and for the "take" branch I appended a "t". You can use this string in debug print statements to find your bearings.