Question

Ps8, dpAdvisor: Any suggestions on what to use for a memo key? I looked at the example in the handout and can't map it to the ps8 problem.

Answer 1

I'm just starting that problem now. My understanding of memos is that they should save the combinations that have already been tried.

So here's a thing, and you can tell me why it won't work: I just tried using tuples as dictionary keys, and that DOES work. I figure that I should be able to save a dictionary entry each time I try a combination, in which the key is a tuple of the class numbers, and the value is the total value. That way I can look through the dictionary at each iteration to see if I've already tried the remaining combinations along that branch of the decision tree.

I forsee running into some confusion because the elements in the tuples may not be ordered in a convenient way, but I think I can overcome that.

Answer 2

Grrr. My first response just got swallowed up by the system. Trying again (and it was so well put the first time; sigh). I use a tuple consisting of three values: i (the index into the subjects list), subsetValue, and subsetWork. That seemed like the "state" at each pass. Of course, it's possible that that is a good choice, just poorly used. I check the memo at the beginning of the main "else" clause; I wonder if I should check it the beginning of the function itself?

Answer 3

So what would an example value of i be? I don't understand how you're recording which combinations of courses have been evaluated.

Answer 4

The call to dpAdvisorHelper includes the index i, initially 0. What I did was look at how the knapsack example in the lecture was memoized. Basically he took the brute force algorithm and just memoized every return value. I did the same thing--I took the bruteForceAdvisor code, copied it into dpAdvisor, and memoized it.

One parameter is the index i, which is incremented to traverse the list of subjects. It's tested at the entrance to dpAdvisorHelper and if there are no more subjects, the current "best" values are returned. I'm in no position to say this is all correct, just that that's where I am right now, and it's not quite working. I'm inclined to think the problem is how I'm constructing a meaningful key for the memo.

Answer 5

Grrrrrrr. Another post got swallowed. Note to self--copy to clipboard every post before clicking the Post button...

Here's what my save step looks like:
memo[(i, subsetValue, subsetWork)] = bestSubset, bestSubsetValue

And now I'm thinking the subsetValue component of the key may be superfluous.

Answer 6

It sounds to me like your program would be testing the courses individually rather than as combinations. For instance, when you test Subject 6.00, it sounds like the tuple returned will be something on the order of ('6.00',10,1) (my values are plugs--I didn't actually look up the entry.)

When that value gets tested, it sounds like you'd end up with either just the single 'best' subject, for whatever you're trying to optimize for, or a list of subjects from best to worst.

Although I've been looking more closely at the handout for the knapsack problem lecture, and I'm starting to think I'm either on the wrong path or on the right one but on a seriously inefficient branch.

Answer 7

So near and yet so far...

I just finished a program based on findMaxVal from the knapsack lecture. Based on results of small inputs from the brute force algorithm it's working, but it only returns the maximum value, not the combination of elements. Maybe I should've paid attention to what that function said on the box. back to the drawing board...

Answer 8

I'm getting five courses back when I give it the full catalog and maxWork = 5. Oddly enough, 4 of the 5 are the same in the brute force and the memoized version, but one is different. The memoized version is clearly wrong, because the result is suboptimal (less value, same amount of work, as compared to the brute force result).

Answer 9

Ta-Da! Problem solved. Solution available on demand. Hint: I wasn't using enough information in the tuple that made the key to the memo.

Answer 10

nice! I think I'm almost there. I just went through and commented every single line of code to make sure I knew what it was doing, with the result that I think I'm where you were 9 hours ago.

Answer 11

Good luck. There's nothing like figuring it out for yourself, but let me know if a few more hints would be welcome.

Answer 12

Also, just a performance improvement note. I ran it with maxWork = 8 against the entire catalog. Brute force took 14.9 seconds, dynamic 1.3 seconds. I guess that's a non-trivial improvement, eh?

Answer 13

wow, a threefer. :)

Answer 14

yeah. Partway through I had an algorithm that was finding what I think was the correct total pretty quickly but was still ^n to find the actual subjects. I set it working on 80 and went to have dinner. When I came back I realized I'd started a process that might actually take more than several lifetimes. Weird feeling.

Answer 15

Well, enjoy. I'm giving myself the rest of the night off for a reward.

Answer 16

I'm still stuck on this. I'm having trouble visualizing the way this kind of recursion works. In the Fibonacci example, the memo was defined globally, but in the maxVal example it was an empty dict argument. I don't get how the memo gets passed up through the recursive functions so that each iteration can try to return an answer from the memo. I'm not even sure if these are the right questions to be asking.

Answer 17

Got it. Only took a week and a half, too!