dynamic programming practice algorithm

0
votes

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

  • Finding recurrence relation for G[H, j], where G[H, j] is the sum of the grades obtained by spending H hours in total on the projects for courses 1, 2, ... j
  • Finding a dynamic programming algorithm that computes G[H, n]

Does anyone have ideas?

1
algorithmdynamic-programming
This is just the unbounded knapsack problem in disguise. – mfjones

1 Answers

1
votes

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