Question

I'm having trouble with problem set 8 about dynamic programming I've re watched the lecture and still dont get it. Do you know of any other resources that would help?

Answer 1

ohh. i haven't seen the problem??
where sre you finding difficulty??
http://www.youtube.com/watch?v=2DZatj5gCo0
this video is good. you must see it.

Answer 2

hey, i'm also stuck on this problem. all the other psets have been cake up until this point. would you be interested in gchatting/skyping to figure it out?

Answer 3

this offer applies to anyone else stuck on pset 8, too!

Answer 4

It is a knapsack problem
you have to keep track of the actual items taken - not just the value and work/size
understanding the process of 'walking thru' the binary decision tree was key for me:
i made my own set of items and 'drew' the tree over and over till i understood it
each node in the tree is a decision point in the code - also a point for possible recursion
i watched the lecture with the maxVal and fastMaxVal functions many times
I adapted the fastMaxVal function to the dP solution of PSET8
i split the dictionary into three seperate lists

there is a faster algorithm - it does less work - there is a youtube video for it and it is promoted as dynamic programming, it memoizes but it isn't recursive - it uses two 2-d arrays/lists seems to be different than dynamic programming but similar - and it works (at least for the 0/1 knapsack problem) so ....

one day i'm gonna have to watch all those lectures that pop up on youtube for "dynamic programming"

Answer 5

Hi guys!I have somehow solved that task fast but there is a bug I couldn't fix.Maybe after seeing my code you would get some insight(mainly look for changes I made).For details follow the link: http://openstudy.com/study#/updates/504df173e4b02f46fa899394