CODEWITHSUNDEEP
algorithmdynamicrecursiondynamic-programming
user1025948
user1025948

Reputation:

Having trouble setting up dynamic programming

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

Upvotes: 2

Views: 1106

Answers (2)

Codor
Codor

Reputation: 17605

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.

Upvotes: 0

Taekahn
Taekahn

Reputation: 1692

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/

Upvotes: 0

Related Questions