Question

PSET 8 problem 4. 6.00 cp 2008 course. I watched the same lecture for a few times and I understand the theory behind the decision tree, but I can't write my own code which mimics the decision tree. How to build it? Because I have done the previous problems quite easily and I am struggling with this one for half a week if not more. In problem 4 I just have to modify brute force function to store the answers in the memo. I might be able to do it, but I want to write the code for this on my own and I find it impossible. Even tried reading the section on dynamic programming on prof. John's book.

Answer 1

most Everyone doing this problem struggles with it and spends a lot of time on it. I eventually scrapped the "modify BruteForce" approach, cause i couldn't make it work. wathced lectures 12 and 13 a number of times. I ended up adapting the fastMaxVal() function from lecture 13 - it mimics the process of walking through the decision tree. I also constructed my own (limited) decision tree and 'walked' it many times till i really understood it.

It is a 0/1 knapsack problem that you have to keep track of the items taken as well as the total worth/value
.
Try something out and ask questions when you get stuck.

I have a collection of different solutions that people have posted here. When you've finished your solution would you mind posting it?

Answer 2

Good to hear that I am not the only one, that means that I might not be totally stupid. I will post the solution today (hope so). I will try to make one of my own, because It would be cheating my self if I would use the function from the lecture.

Answer 3

Ok i give up. I can't create this function. From creating simple functions which added two numbers i need to implement a difficult recursive function which has 8 arguments (we have to modify the bruteforce algorithm which takes 8 arguments. I want to write it myself, but seems impossible). Maybe some day, but definitely not now. How do you learn a thing like this? Every lecture on recursion just talk about simple functions which have a few arguments at most. Such functions are easy to track unlike this one...

Answer 4

you deconstruct the problem and break it up into chunks. you keep trying till something gels.

the solution i came up with isn't the fastest but it works. i chose to split the
{course:{value,wieght}} items into three lists then just kept track of the index being taken.
Again, i gave up on the "modify bruteforce" approach - too much to wrap my head around.

you want a peek?

Answer 5

Yes, I would want a peek. For learning purposes.

Answer 6

The problem is that I don't know how to implement the decision tree into my code. I understand the example with values from the lectures, but now it seems like a different story. Well probably only I don't get it.

Answer 7

Actually, If no one would have said that I should implement a decision tree, I wouldn't have noticed that recursion is a natural way to solve this problem. I just don't see it.

Answer 8

here's mine - http://dpaste.com/1271569/

Answer 9

I was trying in my version to store indices and then loop through them as well. However, unsuccessfully. I tried to mimic your answer and it worked, thanks. Now, even though I finished, I don't understand a few things. The take and dont_take empty lists are in the helper function. So every time you call out take and dont_take, the empty lists are being taken out. At first I tried to put them into the NOT helper function(which we call out). That didn't work, however. Why is that? I think I am missing a crucial point in understanding what is really going on in this function. Moreover, when we reach i==0, if the work of subject is lower than workMax, we store it and return it. Else: we store it as an empty list and return it. Why is returning an empty list important? Because at first I didn't even write the ELSE branch, but without it, it doesn't work. Thank you for helping. I really would want to understand this completely

Answer 10

"Why is returning an empty list important?"
every time the function recurses it does so as an argument to the list extend() method. The extend method expects a list as its argument so the function must return a list (even if it is empty.

" Why is that?"
each new function instance is a node in the decision tree. at each node in the tree two new branches are created - take and don't take. the take and dont_take lists are these new branches (placeholders for the indices that get taken).

if you look at the execution sequence, you can see that each node 'explores' the dont_take branch first. when the bottom of a branch is reached (i==0) the recursion stops and each node returns its result/decision to the node that 'called' it. after the dont_take branch has been explored the node explores the take branch. when the bottom of a branch is reached (i==0) the recursion stops and each node returns its result/decision to the node that 'called' it. at each node, after both branches have been explored, the branch values are compared and the highest value branch is passed up to the next higher node.

if you uncomment lines 61,62,66,72 (from my paste http://dpaste.com/1271569/) it might help get a feel for what is going on. you can put other print statements in to shine a light on the paths. do this with a limited subject dictionary. remember, ctrl-c will stop it.

Answer 11

I tried your uncommented lines. Got some clearance on how the program operates. As far as I understand, the code loops through the dont_take till i==0 and then extends the empty list. At this point it goes further down the code, beyond the dont_take.extend. Then it checks whether to take or not. At his point we reach the take branch. But i is already 0, so it just returns i. How does the i increase, so that it could go up another node? Or does the i in the take functions starts from len(subjects) again? Confused. The lectures didn't explain anything. Is it really this obvious to you? Kind of hard to track back what the function is doing with the lists.

Answer 12

read 9.1, 9.2
http://docs.python.org/2.7/tutorial/classes.html#a-word-about-names-and-objects
adn,
http://docs.python.org/2.7/reference/executionmodel.html#naming-and-binding

each time the function is called a new instance (object) of the function is created. the variables that are defined in the function have local scope.
function x; i= 3 calls function y and passes 2 to y's i variable
when function y returns to its calling function (x), i still equals 3 for function x.

make some simple recursive functions that don't do much and play around in the shell - printing stuff in the function - the id() and dir() built-ins might be useful and perhaps the pprint module.