Question

Suppose you are a high-level manager in a software firm and you are managing n software projects. You are asked to assign m of the programmers in your firm among these n projects. Assume that all of the programmers are equally competent.
After some careful thought, you have figured out how much benefit i programmers will bring to project j. View this benefit as a number. Formally put, for each project j, you have computed an array Aj[0..m] where Aj[i] is the benefit obtained by assigning i programmers to project j. Assume that Aj[i] is nondecreasing with increasing i.

Design a dynamic programming algorithm to determine how many programmers you will assign to each project such that the total benefit obtained over all projects is maximized. Analyze its running time. (algorithm can be written in pseudocode, no specific language needed).

Answer 1

The solution of your problem:
We have to calculate p[i][j] - the maximal benefit we can obtain arranging j programmers for the first i projects.

The base of the dynamics is p[0][j]=0 for all j from 0 to m, we obviously get no profit if programmers do no projects.

For the other values we calculate p[i][j] in the following way:
if we want to arrange j programmers for the first i projects, we first need to arange (j-k) programmers for the first (i-1) projects and then to assume k programmers to the i-th project.

The total benefit we can get is p[i-1][j - k] + Ai[k]. In order to get maximal benefit we should maximaze this sum among all k=0..j and remember the proper k which maximizes this sum (for example put q[i][j]=k). Since the values of p were correct for smaller i, the value of p[i][j] is correct as well. Then, since Ai[j] is nondecreasing with increasing i, the p[n][m] maximal benefit me can obtain aranging all programmers to all projects.

In order to restore the answer we look at q[n][m] - amount of programmers we assume to the project m. Then we have n-1 projects and m-q[n][m] programmers left and, thus, q[n-1][m-q[n][m]] programmers must be assigned to the (n-1)-th project. The amount of programmers for the other projects can be obtained in the same way.

We need to calculate n*m elements of array p, each calculation takes O(m) time. So, the overall complexity is O(n*m^2).

Solution 2.

let p(j) be the number of programmers assigned to the jth project. The quantify to maximize is given by:
f(p) = Sum[A_j(p_j),{j,0,n}],
subject to the constraint that:
Sum[p_j,{j,0,n}] = m.

f(p) is monotonically increasing in m, but is not concave with respect to programmer reassignment when constrained to a particular m. This means that a gradient descent algorithm cannot succeed in general when starting from some choice of p_j. One algorithm that is guaranteed to succeed can take advantage of the monotonicity of f(p):

1) Let p_j = m for all j, such that there is m*n programmers
f(p) is at a maximum in the space where each of the p_j's is confined to lie between 0 and m (monotonicity).

2 )for each project k, compute f(p'(k)), where p'(k) is the assignment p with 1 programmer subtracted from project k. Find the k such that f(p'(k)) is the largest. This is the maximal f for n*m-1 total programmers.

3) set p_j = p_j-1 for the project k.

4) repeat steps 2 and 3 until the total number of programmers is m. You are now done.

This algorithm will run in time O[ mXn^3 ]: Step 2 must compute f n times, and each computation of f is linear in n. Step 2 must be done (mXn - m) times.

Since the algorithm is independent of any properties of the A_j's, apart from monotonicity, the worst, best and average case running times are all exactly same for some of n and m.