[Dogstopper]

Hey all!

This week's algorithm design and analysis will be on optimizing the total amount of points on your homework or work. Given a list of problems of length j, can I figure out which problem(s) to do within a total time T?

For example, each problem is worth P_j points but takes T_j time to do. If I have T hours before my homework is due, which problems should I do to maximize the number of points I receive?

Design an algorithm that achieves this goal and then analyze the time/space complexity of your solution.

[jon.kiparsky]

Then when you're done, put all of your completed work into your knapsack and take it to school...

[Skydiver]

I thought that you got the most amount of homework done by posting all the questions to DIC and various other programming forums and just wait for the results to roll in. O(n) because you can find minions to parallelize the posting operation, have the solutions come in parallel, but you'll have to sequentially assemble the results which will be O(n).

[jon.kiparsky]

I think searching on stackoverflow is also O(n), but with better constants.

[AdamSpeight2008]

The O(1) method

Spoiler

bully a nerd into doing it for you.

Spoiler

Only works it you're intimidation and built like a brick outhouse.

[jon.kiparsky]

What's the time complexity of nerd()?

[AdamSpeight2008]

Doesn't matter to me, as it done asynchronously and I can be doing other tasks.

[TwoOfDiamonds]

Spoiler

Would it work if we would sort them by the Pj/Tj ratio and just get the biggest ratios ?
that would be O(nlogn)

[Dogstopper]

TwoOfDiamonds, no the greedy approach does not work. Let me give you a counterexample.

P1 = 30, T1 = 30, P1/T1 = 1
P2 = 20, T2 = 10, P2/T2 = 2
P3 = 5, T3 = 10, P3/T3 = 1/2

If I have T = 30, then this algorithm will first grab P2/T2 for 20 points and then be stuck with P3/T3 as the only one it can do in the remaining time for a total of 25 points.

If, instead, I did JUST problem 1, I would have 30 points.

[macosxnerd101]

Spoiler

I would apply an MST heuristic. Given a complete graph of assignments, I would have a weight tuple (points, time). I would then apply a Prim algorithm from a given starting node, such that the path would end if time constraint T would be exceeded. For the connected component, I would take the path with the maximal number of points and store it in a set S. For each leaf from the Prim subtree, I would begin again with the leaf as a starting node and apply the Prim Heuristic again. Then I select min(S).

The time complexity is O(V log V).

[Dogstopper]

Neat solution mac! Thanks for sharing!

[Dogstopper]

When I solved this problem, I used a dynamic programming technique where I had a 2D table which had j columns (one per task) and T rows. I then used the recursive function M(j, t) which gives the max of the first j sub problems. You can define the recursion as:

M(j,t) = {0, if j = 0 
          max(M(j-1, t), Pj + M(j-1, t-Tj), if Tj < t
          M(j-1, t), else
         }

Translating this recursion into dynamic programming is simple, but the algorithm is O(j*t) in both time and space.