Question

Hey AGAIN guys - stuck on the problem set 8 again, question 4. http://codepad.org/aWTfu673 - It's obtaining the correct value for small dictionaries of classes but I can't figure out how to get the right listing of courses. It's just returning a dictionary with every course available in it. I can write versions that obtain smaller, but incorrect dictionaries and I'm kind of at the end of my coding rope here. Any thoughts or suggestions would be extremely appreciated. Thanks!!

Answer 1

you are memoizing one thing and returning another. That doesn't seem right. I decided to 'save' indices - so i memoize lists of indices that were chosen and my function returns a list of indices. I have to do some xtra processing each time I want to compare the take and dont_take branches but it works.

You are very close - I have seen a lot of implementations and I believe that the thing that is memoized always contains the thing that is returned.

The purpose of the memo is to 'short circuit' the rest of the code if it has already figured out the answer for the current set of criteria - if it has it can immediately return the answer. So it seems that the memo should contain the thing you are looking for. It looks like your memo only contains a list of values which for this purpose is meaningless - there is no subject information in your memo. Your memo should contain the same information that you want to finally return to the caller.

You have a couple of disconnects:
with_i and without_i appear to be a single, total, value. that makes them easy to compare in line 32 but they don't seem to have any relationship to your memo or chosenNames. Then there doesn't seem to be any permanent relationship between your memo and chosenNames

You probably want to rework it so that your memo and with_i and without_i have the same data structure and dispense with chosenNames- again, the idea of the memo is to immediately return the data/answer without having to recalculate it

I hope that made sense.

Answer 2

I agree with bwca. Your memo only contains the values computed by the function. However, your function returns both the values and chosenNames(which I assume is your 'best' set).

The purpose of memo is to store the previously computed results by your function. So if the result for the given (i, maxWork) had already been computed, the result will just be fetched from the memo. If not, then the function needs to compute it AND store in the memo. The fetching instead of computing part part is what makes the program run faster.

If your memo only stores one of the items being returned, which in this case is the best set's value, the program needs to be called everytime just to compute chosenNames. This clearly defeats the purpose of the memo. The point is, you have to store everything that your program returns inside the memo.

I found this link from the Readings: http://20bits.com/articles/introduction-to-dynamic-programming/. It helped me understand the concept a lot. I this helps.