Question

I'm stuck at dp problem #4 for ps 8
It takes way too long for maxWork >= 7 or so, on 320 items(subjects) in the provided subjects.txt file
Code's at http://ideone.com/dpt8V
Could someone tell if it could be optimized further ? I've checked a few posts that talk about a Matrix solution ,etc. but I would like to fix solution in code above. I'm probably missing something trivial in my code that's taking up too much to generate the result /solution I'm stuck at dp problem #4 for ps 8
It takes way too long for maxWork >= 7 or so, on 320 items(subjects) in the provided subjects.txt file
Code's at http://ideone.com/dpt8V
Could someone tell if it could be optimized further ? I've checked a few posts that talk about a Matrix solution ,etc. but I would like to fix solution in code above. I'm probably missing something trivial in my code that's taking up too much to generate the result /solution @MIT 6.00 Intro Co…

Answer 1

you are not memoizing anything which is the defining feature of dynamic programming,

watch the end lecture 17 (start about twenty minutes into it) and the beginning of 18 again.

Answer 2

I don't get it. I didn't go through the video lecture yet it but I think grasped the basic idea . I read the wikipedia entry on memoization, and if you look at the code carefully, I store values for later use on line 79 and check on line 75 if it already exists avoiding another recursive call. What more will memoize do ?

Answer 3

put lots of comments in your code so we can see what you intended - this problem is hard enuf to figure out.
or explain how the two functions work to accomplish the task; citing line numbers in the code line numbers

Answer 4

Here http://ideone.com/ALsx9

Answer 5

@ bwCA I figured out the problem. I setup the memoization conditions and steps but the program doesn't ever make use of it. Thanks for pointing out the it doesn't memoize anything

Answer 6

post it, i like to see solutions to this one

Answer 7

I shall definitely post my solution as soon as I'm done. Currently, I'm still working on it

Answer 8

Here's a solution I've worked on but works only till maxWork < 20
I'm not sure if I get the right answers for the values from 10 to 20 but I tested it with a smaller subject list i.e of size 4 or 5. I get the right answers then. For the subject list of 320 items, my solution takes too long to compute an answer and I stop computing the answer mid-way, as it eats away a lot of memory only when I give maxWork a value of 20 or more

Answer 9

The solutions I get from the code in the attachment with maxWork = 6,7,8,9 with subject list given for the problem are incorrect. Ignore the code in the last attachment

Answer 10

i don't understand what lines 150 thru 159 do - could you explain in words?

in the for loop that begins at line 150 you call dpAdvisorhelper multiple times (line 156) -
in turn dpAdvisor helper is calling itself (probably multiple times) at line 204. this seems like too much. I think tou might be doing too much in dpAdvisor - most of the solutions i have seen only call dpAdvisorhelper once from dpAdvisor. Are lines 150-159 an optimization strategy?

at line 144 you 'fill' li with the list of subjects using list() why don't you just use subjects.keys()?

Answer 11

I finally got a working version of my previous file but it takes way too much time starting from maxWork == 7

Answer 12

Yes, I might be doing too much in both dpAdvisor and dpAdvisorHelper. I have to think of the design once more.

Answer 13

using li in line 144 gives the same result. calling 204 is the crux of the solution. in lines 150-159 , i check for the first item in subject.keys() whose work doesn't exceed maxWork and in fact less than maxWork, and then break to avoid checking further.

Answer 14

What I'm essentially doing or would like to do is the following:
let us say keys are [1,2,3]
and let us assume all keys have corresponding value of work less than maxWork
Line 204 does [1,2,3]-> [1],[2,3]->[2],[3]
Now I get the combination[2],[3],[2,3] after the last arrow and would then add those to [1] to get
[1],[2],[3],[1,2],[1,3],[1,2,3]
Out of the above, it's easy to find the one associated with the maximum Value

Answer 15

Here's a working solution that takes nearly 10 minutes for maxWork of 10
Hahaha. I think there's no memoization really in this solution

Answer 16

The subproblems are solved and solutions from each are composed from last function call to the first.

Answer 17

are you saying that you are making all combinations of keys whose work is less than maxWork, then comparing those combinations?

Answer 18

less than or equal to maxWork. Here's an optimized version of my last solution

Answer 19

Finally, I've solved it. You wouldn't believe this. Lines 215 and 218 caused a delay of two days. I didn't have them before but affected the solution. Implementation issue even though the idea was right. Most importantly, I 've only started to make use of the approach of memoization only after I've actually started to accept the solution given @ http://20bits.com/articles/introduction-to-dynamic-programming/
I worked it on by hand on paper to convince myself that it covers all possibilities, had to write down all cases explicitly that might be possible starting with smaller input i.e, not more than 3 to 4 subjects.
That helped a lot. Nearly a month and a week or two later, I've solved it. It is ridiculous. I would have solved it way too sooner if I had spent enough time trying to understand the text in the above mentioned link thoroughly.
I couldn't believe that I didn't realize I was solving a brute force problem and tweaking that under the impression that I've actually implemented memoization technique for DP.
Here's the breakdown:
15 days : tweaking brute force approach of dp
10 days : poor design for memoization approach
1 day: perfect implementation except for lines 215 and 218
today: debugging done to figure out lines 215 and 218 are necessary
(there might be other ways to do this)

* all days with plenty of breaks and less than an a hour or two spent on it per day

Answer 20

congrats. i learned a lot on this one.

if you want other ppl to see this and comment - you should create another post. i'm probably the only one that will see it cause it is so old and i'm the only other person in the conversation.

give me a few days to play with this. i'll post mine and another method later