Ask your own question, for FREE!
MIT 6.00 Intro Computer Science (OCW) 11 Online
OpenStudy (anonymous):

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/

OpenStudy (anonymous):

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

OpenStudy (anonymous):

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.

OpenStudy (anonymous):

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

OpenStudy (anonymous):

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.

OpenStudy (anonymous):

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() ;)

OpenStudy (anonymous):

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

OpenStudy (anonymous):

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....

OpenStudy (anonymous):

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?

OpenStudy (anonymous):

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

OpenStudy (anonymous):

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. :)

OpenStudy (anonymous):

@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!

OpenStudy (anonymous):

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

OpenStudy (anonymous):

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.

OpenStudy (anonymous):

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

Can't find your answer? Make a FREE account and ask your own questions, OR help others and earn volunteer hours!

Join our real-time social learning platform and learn together with your friends!
Latest Questions
laylasnii13: Can i dm anybody to vent having a rough time ??
8 hours ago 1 Reply 0 Medals
kaelynw: starting to draw a hand
8 hours ago 15 Replies 2 Medals
Twaylor: Rate it :D (Took 2 days)
8 hours ago 7 Replies 0 Medals
XShawtyX: Art, Short Writing Assignment: Imagining Landscapes
8 hours ago 4 Replies 1 Medal
XShawtyX: Chemistry, Help ud83dude4fud83cudffe
1 day ago 13 Replies 1 Medal
kaelynw: tried a lil smt, the arm is off but i like the other stuff
1 day ago 27 Replies 3 Medals
kaelynw: art igg
1 day ago 14 Replies 1 Medal
Can't find your answer? Make a FREE account and ask your own questions, OR help others and earn volunteer hours!

Join our real-time social learning platform and learn together with your friends!