For ps8: I'm having trouble wrapping my head around what I'm supposed to 'memoize'. I'm also not sure what code I should use to do it. My guess is that I'll use the 'bruteforce' algo provided? Run that with a dictionary of something and check to see if problem is in dictionary before trying to solve it? What is the problem though... What is the problem though? Maybe I need to understand how the bruteforce works first (ie. what I'm solving for)? Also, is a 'decision tree' used for anything other than just conceptualizing a problem? Thanks ahead of time!

Question

For ps8:  I'm having trouble wrapping my head around what I'm supposed to 'memoize'.  I'm also not sure what code I should use to do it.  My guess is that I'll use the 'bruteforce' algo provided?  Run that with a dictionary of something and check to see if problem is in dictionary before trying to solve it?  What is the problem though...  What is the problem though?  Maybe I need to understand how the bruteforce works first (ie. what I'm solving for)?  Also, is a 'decision tree' used for anything other than just conceptualizing a problem?  Thanks ahead of time!

anonymous · Answer

the problem is a knapsack problem

the fastMaxVal function in the lecture mimics the decision tree (very well) with memoization added.

the difference with the problem you will solve and the lecture's decision tree example is that in the end you have to know which items were kept - not just the total value. 

walking through a decision tree yourself, by hand, might help you.

this seems to be the hardest problem for everyone and typically takes a while to figure out - at least for those that post about it.

anonymous · Answer

Good to know.  I'll put some more time in.  I started re-watching that lecture and I'll finish and see how she goes...