Question

ps8, problem 4, I assume dpAdvisor should be a rewrite of bruteForceAdvisorHelper. Any suggestions?

Answer 1

i tried that and eventually abandoned it - but it should be feasible. I ended up using fastMaxVal from the lecture as a template. An important difference between this problem and the knapsack examples given in the lectures is that this solution must keep track of the items taken not just their weight/value.

This problem takes a loooong time to solve for everyone.

Answer 2

bwCA, thanks. This is going to take a while.

Answer 3

@mkorangestripe, dpAdvisor should not be a rewrite. It's an additional function that you will compare the performance to the bruteforce function.

@bwCA, i just got done solving it. My solution needs to be cleaned up but it works. I used the fastMaxVal template which returns the maxValue and you can also return the memo that saved all the computations. With those two pieces of data you can trace back through the memo to get all the indices of classes to take.

Answer 4

This is by far the hardest problem set in the course, I believe.
@TexasBread Could you post your solution after cleaning it up a bit?
@mkorangestripe I ask the same thing, whenever you are done with it.
I really like to see different implementations of this problem set, given its difficulty, every answer I saw so far is different in some level, quite nice to analyze :-)

Answer 5

i second that

Answer 6

So I read using globals and functions with a lot of arguments are bad practice. The functions I use take a ton of arguments and look really messy. Any advice of how to reduce the number without having to use globals?

Also, I don't like dealing with dictionaries so I convert them all to lists before messing around with them in my functions. Do you have any input whether this is bad practice?

My variable names are confusing too. So any advice on that? Anyways, here it is

http://codepad.org/GX5HMdvw

Answer 7

@ TexasBread: your dpAdvisor is huge in size... about 15 lines should be enough for this problem.

I posted a heavily annotated version of my solution: http://codepad.org/cWmIB8l6

I hope it helps. Feel free to ask.

Answer 8

^ Link's not good anymore, please use this: http://codepad.org/Krm2BRz6

Answer 9

huh.. you're talking about the twentybits article? i wish i head read that more closely the first time- that technique is way more efficient - once through. i had a pre-conceived idea of what that dp algorithm should look like and was stuck on using a dictionary for memoization and duplicating the decision tree process *&^$

Answer 10

@TexasBread would you post your dictionaryToList function?

Answer 11

@bwCA, dictionaryToList function
http://codepad.org/Fs4IicjV