Question

Hi, I'm working on the dynamic pg version (pb4) of the subject selection assignment in PSet 8. I reused the fastMaxVal code of the Knapsack problem and simply added a binary vector (objects) representing the list of objects. Here is the code. It fails to stop when the upper limit is reached however (ie the maximum number of work hours). What am I doing wrong?

http://dpaste.com/752383/

Answer 1

add a print statement to see what is happening to aWork
http://dpaste.com/752464/

here is mine
http://dpaste.com/752465/

Answer 2

Is the purpose of objects to keep track of which items to include by having a value of 1 in objects[index] when it is to be included? If yes, then it won't work using your implementation because fastMaxVal mutates (or modifies) objects. This is why in the case when you need to consider with_i and without_i, and you need to call fastMaxVal for each, they mutate objects (i.e marks objects[index] as 1 even if without_i has the higher value). You think your function doesn't stop when maxWork is reached but IT REALLY STOPS at that point. What just happens is that your fastMaxVal function MARKS MORE ITEMS than it should so it appears that you are exceeding maxWork when you print the results. To see what I mean, see this: http://codepad.org/2971OEwu

Another reason why your program doesn't work is because you made a mistake. (See code attached. I marked it with #***)
http://dpaste.com/752477/

One suggestion is instead of marking a boolean list like your objects (this one really won't work if you use the SAME list for every call), return a list containing the class names instead.

Answer 3

Thanks for your help. Yes as kcpaas suggested the binary vector was intended to represent the courses taken (0 when not taken, 1 when taken). And yes I had failed to take into account the fact that lists were mutable. However even when copying the list, it did not work. I then tried as suggested by kcpaas to build a list containing the course names instead but I had a similar problem. The list was built (I could see it when inserting print statements) but not output. The problem was that when calling fastMaxVal I was including in the output, the courses input to that call rather than the output ie the result of the call. Finally it seems to work (I tested it on a small example for which I drew the decision tree by hand). Here is the code

http://dpaste.com/hold/752535/

Many thanks to all of you for your help

Answer 4

One thing that might cause a problem is having the list 'to_take' in your function. I did something similar and, although I was getting the correct answer, I was not getting the optimal one on large lists. I'm not sure if I'm right in my explanation, but... to_take changes, however, the memo entry that is returned does not reflect that change and so may return incorrect values. Compare your results with the one on the handout to be sure...let me know what happens.

Answer 5

If all else fails, try using tuple (which is immutable) instead of list for the set that you will return. Also, the input to_take is not necessary since you are supposed to return, and not input the best set. Just perform concatenation when needed. :)

Here's my code by the way if you want to check your outputs. I included the .py file itself so that you can run it without peeking. Just change the range in dpTime() ;)

Answer 6

I based mine on the bruteForce () so it's slightly different than MaxVal()...but- hopefully- works the same. By the way, I used concatenation for the list too. http://pastebin.com/3urmZzSj

Answer 7

dbwonders, your code returns the correct output but it takes too long to compute the values. It typically takes less than 0.50s for maxWork < 100. Your function works correctly but I don't know why it's taking too long. hmmm....

Answer 8

I thought that too...I just noticed that I only put memos before the 'official' returns. Maybe if I add one more on line 66...Well, anyway glad to hear that it does work. It seemed to have taken alot of messing around before I got something so simple! By the way did you run into any problems when you had the to_take list in your function?

Answer 9

Thanks kcpaas for the code. It is similar to mine but cleaner and I found it very useful for learning to improve code. In particular, I am seeking to improve my comments and yours are very nice, brief but to the point. Thanks

Answer 10

dbwonders, I now know why your code takes a long time to run. You should add an if statement for dealing with items that exceed maxWork. What happens with your current code is that even if an item exceeds maxWork, it computes both with_item and without_item even if it should just immediately return the without_item value and set. No need to compute with_item since if an item exceeds maxWork, you shouldn't include it in the first place. As a result, you have unnecessary recursive calls to dpAdvisorHelper(), and unfortunately, this piles up EXPONENTIALLY with each call.

nataraja, if you only know how messy my code was while I was trying to figure out problem 4. haha! Just a tip: always put comments in if-else statements especially on complicated codes. It helps a lot in debugging. I'm always glad to help. :)

Answer 11

@kcpaas -- of course! That makes perfect sense...I originally had with_item inside the if statement but it was undefined if that if statement was skipped, so just slipped it outside not thinking of the consequences (obviously a bad, not to mention, a sloppy move). As I said earlier, mine was based on the bFA(), so the with and without are reversed. I can see now why there is a difference. Thanks...Will try again!

Answer 12

@kcpaas FYI: result times .25 v 6.85 good call...

Answer 13

I tried running this code that dbwonders supplied, but I get an error. When I go to call dpAdvisorHelper on the without line, I get an error that says 'NoneType' object isn't iterable. I can't paste the code at the moment, but it is basically exactly what dbwonders posted.

Answer 14

I found my problem. I had forgotten to include a return in the base case. The problem is fixed, and it works.