anonymous
  • anonymous
At pset 8 problem 4, I don't know how to map selected subjects into dictionary, can anyone tell me?
MIT 6.00 Intro Computer Science (OCW)
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
katieb
  • katieb
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
anonymous
  • anonymous
I am also looking for help on this problem. I haven't had any trouble with previous problems, but I've been working on this one for 2 days. I attempted to recurse through all subject combinations while reducing the maxwork value for each sub problem as a start to brute forcing it, which worked fine. I then attempted to base the dictionary keys off of the amount of work and the selected subject indeces. This seemed to be capable of solving the problem, but was significantly slower than just brute forcing. I did verify the script was properly using the memo keys. It seemed as though generating the keynames took a large amount of time and due to the uniqueness of the key wasn't really helping very often? Can anyone give us some help here?
anonymous
  • anonymous
@thrift24 this one took me many days. it seems to take most everyone a lot of time. i used the fastMaxVal function from the lecture as a template. there is another way to do it that is not recursive which seems to also be considered a dp solution ). this is a knapsack problem, but you have to keep track of the items that are taken. the dp solution should be faster then the brute force solution I collect ps8 prob 4 solutions :) - post your solution using a code pasting site if you don't mind @FrankVan can you elaborate?
anonymous
  • anonymous
@bwCA I also used lecture code as template and I know how to find the best combination. I write two function for this problem. In the first function I initialized a new dictionary as take it as an argument to the second function. The second function is responsible for finding the best combination. The code is almost the same as lecture. As I had take a that dictionary as an argument, I can put subjects into that dictionary into that dictionary no matter how many times I recurse. The problem is that I don't know when to put a subjects into that dictionary.

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

anonymous
  • anonymous
@bwCA I deleted my old version in frustration yesterday, so I don't have that version any longer, but I did take my 4th or 5th attempt today. I really would like to complete this before moving on or jumping out of a window. Thanks for any guidance you can offer. My dynamic programming attempt uses a significantly different brute force than the example in the file, which I think is causing additional issues as I'm essentially writing both the brute force and dynamic solution in the same pass. It would be great to modify the brute force option that is already there, but I think the code is practically unreadable (totally nondescriptive variable names like "s" and "i", with one comment) My version gets the correct solution, but takes far too much time. I'm not sure if it's my brute force approach causing the additional time, the generation of the dictionary keys for the memos being overly complicated, or that I'm not using the dynamic programming efficiently. Most likely some hybrid of the 3. I think I picked up the necessary concepts from the lecture, but the lecture was extremely frustrating to watch, because the focus wouldn't show the code for very long and so I never got to wrap my head around some real working code. I imagine there are some examples in the course materials if I search for them... If I can force myself to look at the problem again.
1 Attachment
anonymous
  • anonymous
ugh I got it to work by modifying the ps8.py implementation of the brute force algorithm. If you then just create the memo's keys from all the "state" information the function would receive which are not arrays, this will work. I still feel a little dissatisfied with the performance of my initial attempt, but I understand the concept and have it working.
anonymous
  • anonymous
you know that there are pdf's of the lecture handouts that have the lecture code? they are in the related resources tab under the 'video window' of the lecture. post your final thrift24 frankvan: can't help without knowing more, you are trying to optimize value while constraining work. so you could choose subjects based on the work constraint - this should produce a lot of subject combinations - then you have to figure out which one of those combinations has the max value. take a look at the fastMaxVal function from the lecture and understand how it works - see if that helps you finish your solution
anonymous
  • anonymous
@bwCA I had finished my solution. I still used the lecture fastMaxVal function as template. What I did is change the memo from {(aw:i):value} to {(aw:i):(value,(List of selected item index))}. Every time the max value is refreshed, the list of selected item will be refreshed too. Now the aw and i key will not only identify the value but also indexes of selected subjects. Finally the program will return me a list which contain the max value and index of selected item. I can then find the selected subjects according to the index. Here is my code
1 Attachment
anonymous
  • anonymous
As requested here is mine as well. Pretty simple, so I'm sure you've seen this approach before.
1 Attachment
anonymous
  • anonymous
also no, I didn't realize there was a link to the handouts. Thanks!
anonymous
  • anonymous
here is a different method it is much faster, using a table/array. no recursion or outright 'memoization' - i thought dp solutions were recursive, but it does make use of previous results which made use of previous results which made us of .... so maybe it is. first one is my implementation, second by puttamalac http://dpaste.com/696436/ http://dpaste.com/696438/
siBerman
  • siBerman
I implemented the same approach as thrift24, it works, but i still reckon it's pretty slow. I'd love to see the Table/array method, but the link has expired... seems like attachments are the way to go.
anonymous
  • anonymous
@siBerman http://www.youtube.com/watch?v=EH6h7WA7sDw here is the dp matrix solution by putamalac http://dpaste.com/722164/ here is mine (trying to implement the video above) http://dpaste.com/722166/

Looking for something else?

Not the answer you are looking for? Search for more explanations.