PS 8 problem 4: I have been trying to use the dp approach to the bruteForce function. It's not working... I think it's because, as presented to us here, bruteForce does not have overlapping subproblems...it creates new problems each recursion (and because I'm using memo stored items in new, unique situations, I'm returning incorrect values). Does that sound right? Back to a MaxVal implementaion?

Question

PS 8 problem 4:  I have been trying to use the dp approach to the bruteForce function. It's not working... I think it's because, as presented to us here, bruteForce does not have overlapping subproblems...it creates new problems each recursion (and because I'm using memo stored items in new, unique situations, I'm returning incorrect values). Does that sound right? Back to a MaxVal implementaion?

anonymous · Answer

I could not adapt the brute force algorithm to dp.  i eventually gave up and switched to adapting the fastMaxVal function.

anonymous · Answer

Well, I reduced the arguments in the bruteForceHelper() to (subjects, maxWork, i, subsetWork, memo), which created overlapping subproblems and added a 'comparison' to return the 'best' answer, which created the optimal substructure...Guess what it looks like? That's right fastMaxVal... Here it is: http://pastebin.com/3urmZzSj

anonymous · Answer

In case anyone finds this thread...Someone pointed out that the above version is too slow. Here is a faster one: http://pastebin.com/VGhWt8s3 Looks even more like fastMaxVal()!