CODEWITHSUNDEEP
algorithmdynamic-programming
cyberkronos
cyberkronos

Reputation: 51

dynamic programming practice algorithm

I am trying to find a recurrence relation and algorithm to the following problem but have been stuck for a few days:

There are a total of H > n hours in which to work on the n school projects (all of which are due at exactly the same time) and you want to decide now to divide up this time. For simplicity, assume that H is a positive integer, and that you will spend an integer number of hours on each project. You have come up with a set of functions f1, ..., fn (a rough estimate, of course) such that working x hours on project i will get you a grade of fi(x) on that project.

May assume that fi(x) does not decrease if x increases and each project will be graded on a scale from 1 to 100.

So, given H and f1, ..., fn, you need to determine how many (integer) hours you will spend on each project so your average grade is as large as possible (max grade).

Does anyone have ideas?

Upvotes: 0

Views: 1818

Answers (1)

Juan Lopes
Juan Lopes

Reputation: 10565

I think this would work:

G[H<0, j] = -Infinity
G[H, 0] = 0
G[H, j] = max(G[H-i, j-1]+f_j(i)) for 0<=i<=H

In the recurrence I'm trying to find the best number of hours to work on the project j. This solution is O(H^2*n).

Upvotes: 1

Related Questions