Having trouble setting up dynamic programming

2
votes

"It’s nearing the end of the semester and you have n final projects to complete. Your goal, of course, is to maximize your total grade on these projects! For simplicity, say that you have a total of H hours (a positive integer) to work on the projects cumulatively, and you’ll spend an integer number of hours on each project.

To figure out how best to divide up your time, you’ve come up with a set of non-decreasing estimate functions {e1, e2, . . . , en}, one for each project: if you spend h hours on project i (where 0 <= h <= H), you’ll get a grade of ei(h) on that project.

Give a dynamic programming algorithm that takes the estimate functions {e1, . . . , en} as input and that generates non-negative numbers of hours {h1, . . . , hn} such that (h1 +h2 +· · ·+hn) = H and your total grade (e1(h1) + e2(h2) + · · · + en(hn)) is maximum. For full marks, justify your recurrence, and briefly analyze your algorithm’s running time."

2
algorithmdynamicrecursiondynamic-programming
Your idea will not work because in general you cannot choose the maximum for every item due to lack of time. You have to make compromises – Niklas B.
I suppose that this is to be understood as e1(0)=...=en(0)=0? – Codor

2 Answers

0
votes

This sounds suspiciously like the log cutting problem as described by cormen in introduction to algorithms. If you don't have it, i suggest picking it up.

Here is one online reference, though i'm sure you can find others. http://www.geeksforgeeks.org/dynamic-programming-set-13-cutting-a-rod/

0
votes

I believe the problem can be solved as follows.

The state space of the dynamic program is modelled as n+1-tuples (h,h1,...hn) such that given h hours in total, e1(h1)+...+en(hn) is maximum. For the initialization, set the values of the states to e1(0),...,en(0) where h=0 (this value supposedly is 0 as not explicitly stated otherwise).

Then iterate over h in an increasing order; intutively, as h incerases, you permit one unit of more time to the solution. As the utility functions e1,...,en are monotonically increasing, the problem is to decide where the extra unit of time should be spent. This means that for h+1, the values of (h+1,h1+1,h2,...,hn),...,(h+1,h1,h2,...,hn+1) have to be evaluated by e1,...en; the choice of maximum value is to be stored.

In the end, the last tuple (for h=H) yields the result.