Question

Argh, REALLY struggling with wrapping my mind around what's going on with the recursion in the brute force algorithm in PS 8. I'm on problem #4. I've followed the logic path and I think I get the idea of where it goes and how it gets all the possible subsets, but I can't figure out what information the memo dictionary is supposed to be "squirreling away" -- how it's indexed and what it's supposed to return. Any pointers on how to see this clearly?

Answer 1

This is a knapsack problem. adapted the findMaxVal example from the dynamic programming lecture(s). This problem requires keeping track of the actual items taken not just the values. I ended up keeping track of the indices of the items taken (subject, value and work were all put in lists).

my memoization statements are:
memo[(i, work_avail)] = [i]
memo[(i, work_avail)] = dont_take
memo[(i, work_avail)] = take
where i is the subject index and work_avail is the amount of work left; take and dont_take are lists of indices taken on branches of the decision tree.

I never spent a lot of time trying to figure out why that key (i, work_avail) was chosen in the example except that it looks like that combination may result in unique tuples - i think uniqueness would be a criteria for a memoization key.

Answer 2

all right, thanks I'll work on this. I was using the findMaxVal() function from the handout as a guide, but I still couldn't see how it translates. one major divergence from the lecture is that during the decision tree (and the findMaxVal example) guttag made a specific point of starting from the last item and going backwards, whereas the brute force algorithm goes the opposite way. I don't understand it well enough to really know how this makes a difference, but I suspect it would make a difference, especially since he made a point of it.

I agree, uniqueness would be a significant part of setting these keys, and I don't really understand how (i, aW) really meets that condition. I guess basically if you find yourself at any given i with the same aW, you'd make the same decision from that point regardless of the exact path you took to get there...?

Answer 3

I couldn't figure out how to implement memoization with the recursive program provided. I gave up and set it up using two matrices like this guy describes ( http://www.youtube.com/watch?v=EH6h7WA7sDw).

Answer 4

for bwCA

well (i,work_avail) are the changing variables that you have to look at, you don't actually want unique with this code, you want the lowest common denominator, otherwise your never going to call your previous answer.
without i your just checking against weight which would look like a greedy solution to the problem, without work_avail then you don't know how much space is left to stuff in the bag, meaning it could be empty it could be full and you'd never know

for the baron
it helps to create a side piece of code just to figure out the value of your list of index, bwCA gave me that advice. it lets you get the value from a list of index easily without needed to store the value. then storing a list of indexes is easier.

also that youtube video is slow

Answer 5

assuming it's possible, i definitely want to try to get it using the provided brute force method. I think it's just a matter of understanding what you're storing and when, and that's the whole point of the lesson. Thanks guys, I'll work through it some more and let you know how it goes

Answer 6

@mk95, that video was pretty helpful to understand the problem though. A completely different way to visualize it than the decision tree.

Answer 7

@Nessman: when you recommend creating side code to figure out the value the "list of indexes", are you talking about the dictionary? Like the one that's referred to as argument 'm' in the fastMaxVal example?

Answer 8

mk95: i tried to implement the method in the youtube video
it seems to work with a 4 subject dictionary but it isn't giving optimized values for a 20 subject dictionary or the full dictionary.

what do you get with the full dictionary and a work constraint of ten?

my comparison - http://dpaste.com/581272/

Answer 9

well our code makes a point not to fill in a cell until necessary, the other (simpler) code insists in filling them all in
the brute force just doesn't fill them in

Answer 10

bwCA: This worked for 30 subjects, which was the example provided in the problem statement. I basically did exactly what was described in the video. Created two matrices and then moved through each cell updating both matrices. Once the desired weight or value is reached work backward to find the right subjects. I haven't taken a look or you link yet, but I will. I'm not 100% confident this right since it's pretty hard to check. But here is what I did.

http://dpaste.com/583822/

Answer 11

Here is full dictionary and constraint of 10. http://dpaste.com/583853/

Answer 12

mk95: does line 27 read like this:?
if the current item's work is less than the current column &
[the current item's value plus
the cell value at (previous row, remaining weight)
is greater than the previous row's value in this column]
then do some stuff.

Answer 13

well i obviously have a bug in mine but when i compare mine to yours i can't see it, they look the same (algorithmically) - i'll look harder.

Answer 14

I think i found the problem. You weren't accounting for the situation when the courses work was greater than the space available properly. Originally it read
else:
## print thisitemswork, '>', col
# this item won't fit
continue

When it should read thisvalue = vArray[row-1,col] instead of continue. Otherwise it was just keeping a zero there. I made a couple of other minor changes, like changing to an numpy array so you can see whats going on more easily. But I think that was it b/c now it matches mine for full subject list and work of ten (also matches example given of 30 in HW).

http://dpaste.com/588173/

Answer 15

here's the .py file

Answer 16

well, I worked really, really hard on this problem for the last 2 weeks (I hate to say, probably about 70-80 hours), and I just could not figure out how to maintain the optimal subset properly with dynamic programming. I got to the point where it would produce the correct optimal solution, and include all of the correct subjects, but would also include some extraneous subsets in the list. Thanks mk95 for the code for your solution; that will prevent me from losing my mind -- I understand how you did it, I Just wasn't able to implement the tree myself. As absurd as it sounds to spend that much time on the problem, I feel like I learned a lot about debugging and tracing the code logic and stuff; Problem Sets 9 and 10 were a breeze!

Answer 17

baron - if you aren't sik and tired of this problem ... here is my original solution that used a variation of the finMaxVal function from the knapsack lectures - have a look and compare if you want.

Answer 18

mk95 - thnx. i went back thru the video and he never does that or mentions that it needs to be done when an item won't fit ... i was just implementing what he presented without thinking about it :)

any way, looks like thats it thnx

Answer 19

hey bwCA, thanks so much for posting this code. This is pretty much the same approach I was trying to do on the problem, but wasn't able to. Quick question though, when you return or append [i], what does that mean? I was playing around with it in the python shell, and it seems like it just returns the value of i with brackets around it, as though it were a list with only one element. Is there a particular use for this structure here?
Thanks again, it's really great to be able to approach this problem again, because I REALLY wasn't intending to ever look at it again.

Answer 20

bwCA, thanks again for your code. It turns out, just like between humans and apes, my code was about 99% similar to yours. I was trying to implement from the same maxVal blueprint in the lecture notes. What a difference 1% can make.
I guess my main issue was that I didn't know about list.extend(), which seems critical here because you're able to zero out your list at each function call and then add the whole memo entry all at once. It didn't even occur to me to look for something like that. I think the fact that I was unable to zero out my best subset list is what was causing my troubles of repeated and extraneous items kept in the list.
Also, it was really nice to just track the subset and then add the subset value together in the dpValue() function. For some reason that never occurred to me and I was trying to track bestSubset and bestSubsetValue like in the brute force function which was really confusing to implement.
Other than that, I was pretty much on the right track. I guess full closure would be for me to use the concepts from your code and update my own, but I don't think I've ever been this burned out on a problem in my life... :)

Answer 21

so.... i guess you figured out why i was returning a single item list in the recursion base case? i needed to be able to work with single indices (for the base case) and multiple indices (which, because a chose a list as my data structure, would be a list of many indices coming back from a branch). I didn't really go looking for the extend method functionality - because a chose a list, i was reading all the things that were possible for lists and there it was.

fwiw, the matrix solution that mk95 showed us turns out to be about 10 times faster than the 'following the decision tree' solution - and i have since seen someone else that used that algorithm - now i'm trying to reconcile that method (which purports to be dynamic programming) and the method we were shown and the stuff i read about dynamic programming.
I'd like to be able to know when to use the algorithms - i wonder if the matrix solution is a knapsack 0/1 specific solution with some memoization thrown in and what we were presented is a more general solution .. anyway, anyone that has a thought on this chime in pls. how do you translate 'overlapping subproblems with optimal structure', into that matrix solution?