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.

Answer 15

Mandarin question - I am writing a professional e-mail to a Chinese family-friend

Answer 16

calc III: volume of parallelepiped u200bA(0u200b,0u200b,0u200b), u200bB(3u200b,1u

Answer 17

The Life of an African American

Answer 18

Evaluate the extent to which the industrial and business leaders of 1865-1900 should be characterized as robber barons or captains of industry.

Answer 19

Anyone who wants to add me on Snap xxx420kay and follow me on Insta cutie420_love

Answer 20

don't mind me

Answer 21

In at least 100 words, explain why Gatesu2019s premise that the authentication of

Answer 22

It was unusual for women during Kate Chopin's time to be independent. Through her portrayal of Louise in "The Story of an Hour," Chopin hints that independe

Answer 23

Tim, Paco, Maria, and Jenny are standing in line for lunch. Jenny is standing between Paco and Maria, and Pacou2019s position in line is an odd number.

Answer 24

What was revealed about Germany when the British intercepted the Zimmerman Telegr

Answer 25

someone help asap plz!!!

In a graph with several intervals of data, how does a c

Answer 26

plz help me! Bryan was given the equation y= -5x+3. He says the rate of change is 3 and the initial value is -5.

Answer 27

Which task would most likely be completed by a fraud examiner?

Answer 28

. What does doubling the coupon of a bond do to its yield?

It halves the yield.
B.

Answer 29

The largest state in the US is Alaska, covering 663,267 square miles (including water).

Answer 30

What does doubling the coupon of a bond do to its yield?.
It halves the yield.
B.

Answer 31

Can anyone request for me to make photo edits. I'm doing this for fun!!

Answer 32

The Importance of Being Earnest
Which Victorian attitude does this passage highlight?
A.

Answer 33

Which Victorian attitude does this passage highlight?

Answer 34

How does Paragraph 5 refine the claim that u201cthe text on the package does not always tell the whole storyu201d about pet food?

A.