Questions

Dynamic Programming

You are running a software$-$development company, and employ N programmers. You have M ongoing projects, and each programmer can only be assigned to

work on one of them. Each project will produce a different amount of expected profit, depending upon how many programmers are assigned to it$.$ The total

profit from a project, p$,$ with n programmers assigned is $P(p,n).$ You want to assign programmers to projects so as to make as much profit as possible.

a$.(5$ pts$)$ State the function to be optimized, with its inputs and output value, as well as whether this is a maximization or minimization problem.

b$.(5$ pts$)$ Define the above function using a recurrence relation.

c$.(5$ pts$)$ State the base case of the above recurrence.

d$.(5$ pts$)$ State the time complexity of the dynamic programming algorithm based on the above recurrence.