Question

I am struggling with the dynamic programming subject selection in problem set 8. I can write an advisor that will return the maximum value of the knapsack and meanwhile create a dictionary of the form (i,maxwork):(maxvalue), where i is the subject number (subjects.keys()[i]). However, I can see no clever way to create a dictionary with the subjects to select (I don't even know whether to create it while running the advisor or later, just based on the memo). Can anyone help?

Answer 1

well, you need to keep track of the items that are taken (the subjects) and you also need to be able to determine the value of any set of subjects that are taken so that you can compare the different sets (or branches if you like the decision tree example).

I decided to only keep track of the subjects - then i had an extra function that would return the total value of a list of subjects so that i could compare two different lists.

i kept track of the subject indices in a list and my memo had the form
(i, work_avail):[list of subject indices]

i used the fastMaxVal function from the lecture as a 'template'

when you get something written post it - this one is a hard one.

you might want to put something like this at th bottom of your module - to have a couple small dictionaries to work with - http://dpaste.com/668126/