Question

hey im having a bit trouble with ps8 problem 4...
i get the way dynamic programming works. I used the algorithm provided in the handout and also understand how the recursive works but really the recursive really provides the max value only but doesnt really indicate the components that make up that max value.
May i have some suggestions? or do i have to use a different algorithm to solve it?

Answer 1

I just completed this problem.

My first approach was to take the brute force advisor provided in the problem and modify it into a dynamic programming algorithm. That didn't work out to well and the fact that the function passes the subset, subsetValue and subsetWork was really messing up my thinking process.

If this has been your approach as well, my avice is to step back and rewrite bruteForceAdvisor(subjects, maxWork) and bruteForceAdvisorHelper(subjects, maxWork, i, bestSubset, bestSubsetValue, subset, subsetValue, subsetWork)

I wrote MyBruteForceAdvisor(subjects, MaxWork) and MyBFHelper(WVList, i, MaxWork) where WVList was my name for tupleList (the subjects.values() list). Once I did that modifying it into dynamic programming algorithm was fairly easy.

The Memo keys are tuples of (i ,Work) while the Memo value are ( List of Selected Subject, Value of Selected Subjects)

Hope this helps and Good Luck!

Answer 2

Hm...no my approach was to utilize the algorithm provided in lecture 14 and I managed to get the max Value out of it (by the way that algorithm has a REALLY nice recursive)
By the way, somehow when I ran the bruteForceAdvisor provided in the ps, I got no answer (the algorithm kept running without giving me an answer...) so I basically...ignored it...I'll have a look at it then :)

Answer 3

@ ewsmith : http://ideone.com/HCW4x
It takes way too long for maxWork >= 7 or 10