Question

So, I'm stuck at ps8, specifically the dynamic programming problem. First rule of the thumb for using dynamic programming is to find a sub-problem and structuring it in such a way that the optimal solution for it is the optimal solution for the whole thing, hence optimal substructure (With the help of memoisation).

Answer 1

(cont'd)

Problem now is, I can't find seem to find sub-problem. However I noticed that the brute-force alogrithm runs through the entire list even after it reaches the work threshold, so is that it? Stop the algo when it reaches the limit and is the solution simply to sort the tuple list (Holding the value,work combinatiion) according to the work value to ascending order?

Gladly appreciate the help.

Answer 2

Hold that thought for a moment, I just realised that the solution I suggested would be exactly the same as a greedy algorithm. Not very optimised.

Answer 3

what category of problem is ps8?

Answer 4

Dynamic programming: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/assignments/pset8.pdf

Go to problem 4.

Answer 5

is it a traveling salesman problem?

hmmm ... it looks like you have two choices - to take a class or not take a class. you have to make that choice for every class. each time you choose to take a class or not, it will effect subsequent choices - you have to compare those two choices (combined with their subsequent choices) and decide which one is better. i imagine that the lists of subsequent choices overlap somewhat.

Answer 6

Thank bwCA for the reply. The question however is a knapsack problem. But I guess we could frame it to a travelling salesman problem. Many thanks for that.

Answer 7

maybe it is a knapsack problem after all ...
kinda like that fastMaxVal thing in the lecture?

Answer 8

GoonDu: Are you still having trouble with this problem? I put in about a week of intense work on this d*mn problem before getting it all sorted out. It's by far the hardest problem of all the problem sets, unless I'm missing completely missing the trick. I thought I could just take their brute force implementation and add a memo to it, but I couldn't get it to work. I couldn't keep my head wrapped around the 10 different parameters they were passing in, and the 2 return values, all while tracing through the tree of recursive calls. I ended up completely re-implementing a brute force solution that I could squeeze the memo thing in to.