A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • 4 years ago

At pset 8 problem 4, I don't know how to map selected subjects into dictionary, can anyone tell me?

  • This Question is Closed
  1. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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?

  2. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  3. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  4. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @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
  5. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

  6. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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

  7. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    @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
  8. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    As requested here is mine as well. Pretty simple, so I'm sure you've seen this approach before.

    1 Attachment
  9. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    also no, I didn't realize there was a link to the handouts. Thanks!

  10. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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/

  11. siberman
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

  12. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

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

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.