Question

PS8,4: I am having trouble understanding how to implement a dynamic programming approach to the problem. I figure I can adapt the fastMaxVal function from lecture 13, but I don't really understand how that works I think.

Anyways, here is what I am working with at the moment: http://codepad.org/MOze55Ew

It is pretty much just fastMaxVal at this point. Any advice would be much appreciated.

Answer 1

This is the Big One. The Mother Of All PS Questions.

The first thing to do is fully understand the examples from lecture. Then try really hard to decipher the bruteForceAdvisor they gave us (that thing is an atrocious nightmare).

It took me well over a week, and about 50 hours of work, to get it done. Just problem #4. Having an understanding of their examples is not enough. You have to live in the problem for a while.

The two things that helped me the most (I figured these out from exploring the problem more than just working towards the solution):

1. The overall problem is: given a list of subjects, and a maxWork, find something (it's the set of subjects with the highest total value and total work <= maxWork, but that's just a detail). The recursive function calls step down to the next index in the subject list and return another something. So, when you make a recursive call you're saying "With this maxWork, and starting at this index in the subject list, solve a problem." It's the whole concept of STARTING at an index in the subject list that made it clear to me. But the workRemaining parameter gives it a second dimension that makes it more challenging. I worked the problem by hand to see what was going on. I made up 7 subjects, wrote those across the top of the page, and made the different number of hours of work go vertically down the page. Then I looked at the last class, and for each number of hours remaining wrote down the total value it should return. (It gets pretty hard to figure out after about 3 subjects, but there is a pattern that makes it easy, if you can figure it out.) This was highly instructive for me. It shows that each combination of (hours remaining, start index) is a separate problem. Then I wrote a function that could take these parameters and solve that problem. The memoization should be keyed by this (hours remaining, start index) tuple. I also had that function print out this 2-dimensional grid of values, to make sure both it and I got everything right. It was really just a lot of iterative exploration, and trying to fully understand every single little step.

2. Invest some time in writing great print statements. It's incredibly hard to visualize what's going on, so have your program tell you lots of information, and have it print it in a usable, readable format. Since each recursive call makes two recursive calls (skip and take branches) the call stack isn't really a stack, it's a tree, and I couldn't easily find my place in that tree. I had my recursive function take a "path" string parameter, and on each "skip" call I appended an "s" to it, and on each "take" call I appended a "t". I then had a debug string I could use when printing other stuff that would tell me exactly where I was in the tree of recursive calls.

The call stack gets as deep as the number of subjects in the list, so keep it small (I used 7 for testing). And don't be shy about debug printing. But don't overwhelm yourself with output. Add output for what you're interested in, and comment out the other stuff. Like I said, for me it was more exploration than just coding towards the final answer. I couldn't write the answer until I understood how, and that was a long process.

Answer 2

my test dictionary:
test = {'a':(10,2), 'b':(2,3), 'c':(5,9), 'd':(8,4)}

This is a knapsack problem.
I used the findMaxVal function shown in the lecture as a starting point which mimics, very well, the process of 'going through' the decision tree that was presented.

For this solution, you have to keep track of the items taken which wasn't done in findMaxVal - so you need to fix that in yours.

I made my own decision tree for my test dictionary to help me visualize what i needed to do.

Just dive in and keep plugging at it - definitely take the time to write down your ideas before you start and throughout the process.

I also like to make little helper functions that I use in the main algorithm to keep it 'readable'.

my dictionary -> lists http://dpaste.com/640236/

Answer 3

Still working on this. I think I am starting to get how fastMaxVal works. My problem now is figuring out how to save the best picks to a dictionary. I'll keep playing with it and maybe post an update on my code later...

Answer 4

Came across this while catching up on the reading. At the end he talks about the knapsack problem. Might help to check it out. Probably can't hurt.
http://20bits.com/articles/introduction-to-dynamic-programming/

Answer 5

Thanks dmancine. I'll definitely take a look at that. This is by far the hardest problem yet...

Answer 6

I think I understand how fastMaxVal reaches it solution, and have it working in ps8p4 so that I can return the value of the best selection of courses. My problem is I don't understand where/when along the way to store the selected courses.

Answer 7

post what you have - looking at what i did, it seems it would depend on how you did it. Are you just analyzing findMaxVal without any changes?

Answer 8

Just sat down and scratched everything and this is what I've got now:
http://codepad.org/dIttSyVg

I included the output and my test subject list.

I think I am close, but still missing something. I basically tried to mash fastMaxVal with bruteForceAdvisor.

Answer 9

one thing i can see is that you are using maxWork as part of your memo key but you never change maxWork so i don't think that will be effective - there won't be the unique
(i, maxWork) keys for each path through the decision tree. if you watch him go through the decision tree (about 20 minutes into lecture 13) notice that each time something is taken the weight available is modified. also, he starts at the last item in the list - i think that might simplify things (like the base case): you aer starting at the first item in the list.

however, neither of those should make you get a wrong answer.

one reason i backed away from trying to make bruteforce into a dp algorithm was that there were just too many arguments/variables for me to see what was going on.

i didn't really start understanding findMaxVal until i manually walked through a decision-tree while looking at where/how each decision-tree step related to the steps in findMaxVal - i did this a number of times (lots); i'd get to the end and think aha and then later i'd think what the heck was all that? and have to do it again

what is the one thing you can keep track of and in the end know what exactly was taken - not just the value

Answer 10

@bwCA, I came up with a way to help understand where you are in the recursive call tree. I add a "path" parameter, and append an 's' or 't' for the 'skip' or 'take' branches. That way I can print it with my debugging info to see how I got to where I am. Here's a stripped-down version of the problem to illustrate how it might help. I found this to be very enlightening.

http://codepad.org/nQZuFLf1

(I have it just stop at depth 4, or else I could recurse down the skip branch forever.) As you get deeper in the tree the path string grows. And each s or t tells you which branch it took along the way.

Now, if I could just tell python to print stuff out like the professor drew it on the chalkboard...

Answer 11

@bwCA: If I modify the recursive call in line 38 of the code I posted above to subtract s[WORK] from maxWork when an item is taken....not sure where I was going with that, but why would that not work? It looks like that is basically what they do in fastMaxVal...

Answer 12

Most recent attempt: http://codepad.org/CZhWx8Pk

I switched it around so that I start at the end of the list and work my way towards i = 0. I've also modified it (I think) so that the maxWork in the memo keys is unique/updated to reflect the change in work available as items are taken.

Nevertheless, it still isn't quite right. I think I am closer, and I am pretty sure I 'get' what it is doing, I think I've just missed something ,minor maybe? or I'm completely off base. Anyways, thanks for the help so far dmancine + bwCA. Hopefully I figure this out soon...

Answer 13

we are trying to optimize value while constraining work

to work the problem we start with an item and choose to take or not-take it
- this creates two branches,
the take branch affects the work-available and the don't-take branch does not.
- then we go to the next item and make the same decision .... etc

this creates a lot of unique paths/combinations. at some point we have to compare all of those paths to find which one has the highest value (if we did it right, they should all have work values less than or equal to the constraint)

i don't see in your code where you are comparing paths/combinations to maximize value

i made a couple of organizational changes to help me see what is happening better:
http://codepad.org/Mq6eGqHZ
you will notice the differences at lines 30/31 and 43.
there should be a value comparison somewhere in lines 44-54

Answer 14

bwCA: take a look at this: http://codepad.org/C8aidWc7
I moved things around a bit and added a max(without, with) comparison, but it still is doing something funky. Every time I think I get close to the answer I feel like whatever I change takes me farther away in a different direction.

Answer 15

what data type does dpAdvisorF return? how does max handle it?

realize that i am just pointing out things i see and they may or may not be leading in the right direction.

how about stating what these contain:
bestSubset, bestSubsetValue, subset, subsetValue, subsetWork

and give a short synopsis of how you intended dpAdvisorF to work