Question

ps 8.4(revised)
http://dpaste.com/596077/

Answer 1

Works on short lists. does not work overall.
Have tried a number of different things and have spent enough time on this problem so time to move on. Very difficult to trace this many levels of recursion.
The thing I suppose have really learned is what was said in lecture...."it is tough to write a good algorithm". I would add it appears that often it is also tough to make use of a good algorithm:)

If someone have a clean solution to prob 8.4 I would love to see it.

Answer 2

this file has two solutions:
one is an adaptation of the findMaxVal function presented in the knapsack lectures
the other (yutoobAdvisor) is from this youToob video -
http://www.youtube.com/watch?v=EH6h7WA7sDw)

they both work, one is considerably faster

Answer 3

sorry if the comments obscure the code

Answer 4

you figured out that this solution needs to keep track of what is taken. you decided to keep track of that using a global variable - flags. I haven't run your code but i think that will be causing a problem.

All of the recursions ( with and without branches) will be setting flags in this variable. many of the items will be set/cleared multiple times as the algorithm runs through all of the branches. there is no link to the various with and/or without branches that get created or the value comparisons that take place. in line 24 where the value comparison is made, the algorithm doesn't identify which of the items in the flags variable correspond to the winner of that comparison. ... hope i made sense.

Answer 5

You are exactly right CA. This version only works when the "with" branch is selected. At one point I had a global "withoutflags" as well for when the without branch was selected. The problem was (as you correctly mention) because of the levels of recursion and the various switches that occur it worked even worse than the "with" flags.
I also had some solutions that worked (sometimes) in which all flags were cleared at end when "with" or "without" were selected and value stored as dictionary key with courses as value.
I appreciate the earlier tips and the links. Will check out. Ready to see a good answer:)

Answer 6

i attached a file with two solutions in my earlier post.