Question

ps8, dpAdvisor, bug

Something is wrong with my code, but I can't figure it out. I'm having memo return a list that includes both the achieved value and a list (within the list) of indecies that were used. That's what I'm trying to do, anyway. The code always returns a list of courses that come in under the maximum hours, but the value isn't maximized.

code here: http://codepad.org/hVjl1rkR

Answer 1

this seems like a much harder approach rather than following the template from class.

here's my approach:
-extract a tuple of the keys from the subject_dict (I'm using the tuple as an index so I don't want it mutating)
-using the keyTuple, create tuples of work and values.
-then I can pass 'work' and 'values' to the fuction dpAdvisor in the same format as the program in class.

then you just need to add 'i' as one of the returns from dpAdvisor

did you have this working as a regular decision tree w/o the dynamic programming?

Answer 2

what is the structure of the list that dpadvisorhelper returns?

Answer 3

bwCA: should be [ value , [list of indicies] ] where indicies are the i values, if that makes sense

valmont: no, i don't have it working as a regular decision tree. I'm not sure why I decided to do it this way, just seemed like I wouldn't have to make new tuples. If I do it your way, when you say I would just have to add the i values, do you mean a list of i values?

Answer 4

bwCA: that's [ totalValue , [list of indicies] ]

i hate that we can't edit posts

Answer 5

"If I do it your way, when you say I would just have to add the i values, do you mean a list of i values?"

yes. a list of the i value. same as what you're thinking with dpadvisorhelper.

Answer 6

still not working. I think I'm doing something wrong after the else: with_i block

code here: http://codepad.org/HPTXl7ND

Answer 7

I'm a lil strapped for time so quick question.

did you have this working for small files without the dynamic programming?

if not, that might be one way to attack the problem. Get the decision tree working without the dynamic programming first.

Answer 8

btw, I forgot to ask. Do you want me to post functioning code?

Answer 9

you might be right, try recursing (line 83) after you have taken the current i (lines 84-92)
.
you want to take it then recurse - at least that is what i did and your code structure looks similar to mine except for that

Answer 10

valmont: yeah, shoot me some functioning code

bwCA: I'm not sure what you mean. I'm not passing my list of indecies into dpAdvisorHelper and I don't have anything to add the current i to until I get values for with_i back from dpAdvisorHelper. Should I be passing in my list of i's?

Answer 11

btw, I don't know if either of you have ran the code, but the problem is, at least in part, that total value just keeps going up and up and does not match the total value for the final list of indicies returned

Answer 12

dang, got it to work. there was a problem with list assignment, i.e., I wasn't using [:] where I should have been. working code here: http://codepad.org/EqDMjqpf

I kinda went crazy with the [:] -- probably don't need them all, but what can it hurt?

valmont: I'd still like to see your code, if you don't mind

Answer 13

here it is working without the work and value lists: http://codepad.org/SDl3q22n

Answer 14

here

http://codepad.org/OrmQVC24

Answer 15

here's mine, i only kept track of the indices - http://dpaste.com/699640/
and another that uses a different algorithm = not recursive but apparently considered dp
http://dpaste.com/699627/

Answer 16

@six3
i did some testing and yours is faster than mine. yours is linear with work and mine is more-than-linear (curves up) with work. with work = 200 yours is twice as fast.

most of my excess is taken up by having to find the value of each branch with a seperate function because i didn't keep track of it.