Question

ps8_my solution
http://dpaste.com/568930/

Happy w/ "greedy algorithm" but not problem 4. This solution is not optimal and may post revision in next few days if I get time.

Answer 1

If someone has a good answer to problem ps8 problem 4 I would be very interested in seeing it.

Answer 2

it took me a long time. keep it simple.

it is a knapsack problem.
the solution demonstrated in lecture 13 optimized the value while constraining the weight but did not keep track of the items that were actually taken because that was not important for the thief.

in this knapsack problem you have to optimize the value while constraining the work AND be able to come up with a course list.
so it is very similar to the solution in the lecture Except the 'things' that we take ARE important so we have to keep track of them.

keep it simple, if you know (kept track of) just the things you took you can figure out (write a function) how much work it is, what the value is and you can make a new dictionary from it.

If you haven't already done so, make yourself a small test dictionary like this: test = {'a':(10,2), 'b':(2,3), 'c':(5,9), 'd':(8,4)}.
then work out the decision tree on paper just like they did in lecture - it really helps you understand the mechanics/process.
also once you have done this you know what the answer is so you can use it to test your function.

I used the fastMaxVal function from lecture 13 (don't re-invent something if someone has already done it satisfactorily).
- I turned the subject dictionary into three lists (subject, value, work)
- instead of returning/memoizing the value, i returned and memoized the index being taken. i kept the indices in a list and made use of the extend method.
- i had to write a function that returned the total value of a list for use in comparing take and dont_take branches.
- i used the subject list to make a new dictionary from the indices returned by the helper function

Answer 3

Thanks bwCA
I am going to redo problem 4 w/ small dictionary and decision tree as you suggest.
My method works but it really isn't what they are after and I think its important to get this.

Answer 4

WOW...he actually typed that answer!!!....u guys have tons of patience unlike me..LOL

Answer 5

Could someone repost code this this problem set? the dpaste content is expired. I guess really I'm just wondering how you use 'comparator' in the 'greedyAdvisor' function. 'comparator' is a placeholder for a few different functions, each which take additional arguments. I'm not sure how you represent those arguments inside of the code for 'greedyAdvisor', or, really, how to call 'greedyAdvisor'. Is it clear what my problem is?

Answer 6

they are showing that you can pass functions to other functions

to call it,
(from the pset) - >>> greedyAdvisor(smallCatalog, 15, cmpWork)

inside the greedyAdvisor function you use 'comparator'

Answer 7

And in the code, is the syntax for comparator the same as '>' and '<'? LIke you write, 'somevalue comparator anothervalue' and that will return True or False?

Answer 8

No, that's not right.

Answer 9

I think i've got it now, thanks.