Question

Hi, I am doing pset8 from 2008 fall and I'm kinda stuck with the dynamic programming part. Any hints on how to optimize the subject selection in problem 4?

Answer 1

I adapted the fastMaxVal function from the lecture. you have to keep track of the subjects taken as well as the accumulated work an value. I made my own 4 subject dictionary and walked thru a binary decision tree by hand (like in the lecture) many times till i understood the mechanics of that process before i finally got the dP algorithm correct.

there is another algorithm ppl have used that can be found on the net. it involves setting up a couple of matrices (two dimensional lists) to keep track of everything - this algorithm is faster than the fastMaxVal algorithm. and pretty easy to understand - if you are comfortable with the binary decision tree process.