Question

What is going on with the flow of this program? I don't understand this output. Here's the code:

http://pastebin.com/wiXrNMjD

And here's the output:

http://pastebin.com/wvi2i67U

Answer 1

So, without worrying too much about the details, basically the program is a recursive monster and so it's repeating until it gets the answer. But it's the repeating that doesn't make sense to me. As you can see, it starts off with the initial print statements, printing a trio input variables and then a big string of 0s. Then it tests if a tuple is in a dictionary, finds it isn't, then goes to step 3, then step 4. Alright, now it hits recursion: running the program again with the inputs modified. No biggie, right? But WTF? The program prints the inputs again, but skips the second print statement (the string of 0s). It doesn't print either that this tuple is found in m, nor that the tuple wasn't found! Then presumably goes through steps that lead it to recur again, but in following these steps, it doesn't print any of my guide print statements that let me know what it's doing! In effect, it seems to be arbitrarily skipping blocks of code. What's the explanation here?

Answer 2

When you call the function in Step 4 you are using a different function name:
"bestSubset, bestSubsetValue = bruteForceAdvisorHelper(subjects,
maxWork, i+1, bestSubset, bestSubsetValue, subset,
subsetValue + s[VALUE], subsetWork + s[WORK])"
So there is no way to know what is happening unless you include the code for this new function you are calling named "bruteForceAdvisorHelper"

Answer 3

OH MY GOD! You are a lifesaver! It's working now. That is so obvious and now I feel so stupid, haha. Medals to you, and if I knew who you were I'd buy you a beer. :)

Answer 4

post your final solution, including dpAdvisor and any other helper functions if you don't mind

Answer 5

Here it is: http://pastebin.com/tw1HicMc

As you can see, it really doesn't differ much from the provided brute force program; it simply adds in memoization. As such it's a little bittersweet for me because I still don't feel like I 100% understand it (as in, I'm not sure I've internalized the function enough to, say, reproduce the code from scratch) but, it does work. Running with the full 320-line list and a maxWork of 30 takes about 1.8 seconds.

Answer 6

doesn't look like you have an optimum solution - you are not getting the highest value and it doesn't always 'consume' the available work - here is a comparison:
http://pastebin.com/04npHXhb

your memoization might not be working: here are some time comparisons - mine are usually slower than other peoples solutions - yours are much slower than mine
http://pastebin.com/U0HeAyX6

Answer 7

it helped me to create my own little 5 item dictionary and then walk through a decision tree like was shown in the lecture. I did this a lot of times before i finally got a feel for the mechanics of this process.

The fastMaxVal function from the lecture mimics this process - i adapted it to keep track of the items taken, not just work and value.

Answer 8

.... well, drat. I guess I don't have it yet. I don't see why the memoization wouldn't work though - I tested it by having it stop every time it sees a repeated value, and it did this a lot, so I don't see where I could be improving.

I tried to adapt maxVal but I got hung up with the fact that you have to add the items, not just track the value. Blaaaagh.

Answer 9

As for not producing the highest value, that one I really don't understand, because the code that I'm using at the base is really identical to what they gave for bruteForceAdvisor, so there's no reason I can see that the results would be changed. Then again, just because I can't see it...

Answer 10

i can't tell what's going on yet - at line 32 you pop a value from subset just after you appended it in line 27 - why are you getting rid of that index after you had decided to keep it? that looks odd - but again, i don't have a handle on yours yet.

it doesn't look like you are doing any comparisons. i can't help thinking about this using the decision tree shown in the lecture because that is how i solved it. so i'll try to explain and maybe you can relate it to what you are trying to do.

everytime you consider a subject you decide to take it or not take it. that decision point is a node in the tree and each branch from that node results in a different 'value' - further along on those branches there are other nodes - even though the nodes are on different branches they are considering the same items - the difference between the nodes on the two branches is the available work - the two branches overlap - after the value of these two branches has been found you have to compare them to see which branch was better - you keep the best one and memoize it. all of that happens recursively at each node. I don't see where you are comparing the value of two things to find out which was the better path.

Answer 11

The code that I'm using is the same as the bruteForceAdvisor code that came with the problem set, so it might be simplest to look at that code. I see what you mean about the seeming lack of a comparison step but in order for the brute force code to give an answer it must be comparing them. I think that the comparison occurs in the i=0 step, where it sees if the current value exceeds the best value. But, now that I'm thinking about it that way, I'm less sure that it's actually comparing things, or at least I'm less sure that I know how it's doing it.

I've written on paper a decision tree so that I can get a handle on what it's doing, and I feel like I understand the theory OK; it's the implementation that gets me. It probably would serve me best to build it from scratch, so I'll give that a(nother) try. Although at this point it's so frustrating I wonder if I'd be better served by giving it a rest and coming back to it on a fresh brain. :P

Answer 12

OK, on my 4534th attempt at this problem, I have once again come up short. I can generate a decision tree just fine, but I can't translate the damn thing into code. Question - in your explanation, when you say "value" are you talking about the value of a subject, or are you talking about a value like 6 is a value and x is a value? For purposes of clarity, I'll denote the value of a subject as _value_. So, what exactly does it mean for a branch to have a _value_? Because at one point on the branch, you will have one _value_, and at another point further down the line, you will have the same or a different _value_. Every time you branch off, you're presented with a potential new _value_. So, I don't understand how you can compare two "paths", only two "nodes."

OK, all that aside is the practical issue of recording full subjects (which requires three values: subject name, _value_ and work) as opposed to just calculating _values_ as in maxVal. Making this seemingly simple switch is driving me up a fricking wall.

Answer 13

there are two paths you can follow at a node, take it or don't take it, i'm calling each of those paths a branch. in this problem everytime you decide to keep something you have to somehow preserve the item itself so you know what you have kept and its value. when you get to the end of a branch you have decided to keep some things and toss other things - the value of a branch it the total value of all those items you kept. so back to a node - at each node there is a fork creating two paths/branches - one branch you decided to take that thing - the other branch you decided not to take that thing - each of those branches will have a different value because you chose different things - the one with the highest value is the one you want.

fastMaxVal (NOT maxVal) from lecture 13 mimics/implements this process - but it only keeps track of the value - we need to keep track of the items also.

I decided to just keep track of the item indices - i turned the dictionary into a few lists then kept the list indices. when you make lists out of a dictionary using the keys() and values() methods, item 0 in the keys list corresponds to item 0 in the values list. when i needed to compare, i had to call an xtra function to figure out the value based on the indices that i had kept - that's why mine takes longer, other people figured out how to keep track of the indices and the total value of the branches on the fly.

Answer 14

OK, a bit of a conceptual question - fastMaxVal problem keeps a running track of the best value and returns that. But when you're building a list of subjects to include, you have to continually add and remove things from your list of "good subjects" as you find better and better combinations, until the one at the very end is the best combination. How do you manage this process of adding and removing things from your list? Do you not actually add anything to the list until you reach the end of a branch?

...this is the kind of thing where the ability to talk face to face and have someone point at a decision tree and corresponding pieces of code would be SO much easier to understand than a pure text-based explanation T_T but I really appreciate your help on this one. I don't know why this is causing me such a massive brain fart.

Answer 15

each node (the ones near the root and the ones near the leaf) has two branches and a decision is made at each node on which branch was better - this kinda bubbles up from the leaf to the root and when you get to the root it will be optimum. at every node there is a recursion and a comparison/decision - at every decision there is a memoization.

Answer 16

when it finally sinks in you will understand the phrase - globally optimum solution using locally optimum decisions (or something like that)

Answer 17

OK, so I haven't tried implementing this yet, but it seems to me like the concept is you follow your decision tree to the end of the last branch - which means either you're on the last element of your list, or the available work is not enough to add more - and then you use the _value_ that you have in that final node to determine the overall worth of that possibility... am I warm?

Answer 18

Hoookay, I'm back in the saddle again and this time I feel like I'm really close - though it's not working. What I have is essentially a modified version of maxVal, but the idea is that along the way to the highest value possible, as I consider to take or not take each class, I make a note of the result in a dictionary. It gives me the right maximum value at the end, but the dictionary that it keeps is wrong. Putting in some print statements I can see that the reason seems to be that it changes values back and forth (which is fine) in a way that doesn't match up with how it's keeping track of the highest value (which is not fine). I think the issue might be on high I'm implementing the recursion steps - perhaps I should be changing x in some way in the variables I'm calling? Or something. Anyway give it a look if you don't mind.

(don't worry too much about the helper function, all it's doing is making lists of subjects, _value_ and work values and putting them in the function. The calling function is maximumList1.)

http://pastebin.com/fCUQLKJd

The output for a list of five subjects and maxWork of 10:

>>> maximumList1(SD,10)
Value vector: [3, 5, 2, 1, 6]
Work vector: [2, 9, 2, 17, 1]
initial i = 4
___________________

i= 4
i= 3
i= 2
i= 1
i= 0
i= 0
i= 1
i= 0
i= 3
i= 2
i= 1
i= 0
i= 0
i= 1
i= 0
Maximum possible class value = 11
{0: 1, 1: 0, 2: 0, 3: 0, 4: 1}

Answer 19

i won't be able to look at this now but since i did, would you just respond so that it will show up in my notifications next time i get on?

also, this post is so far down the list and you have made some changes, you might want to consider a new post so that others that have completed this problem will see it and might have a different perspective

Answer 20

Yeah, good idea; I'll make a new post out of it.