Problem Idea #7

There are N employees in a firm, numbered 1 to N, and M types of employment roles, numbered 1 to M. Each person must be offered exactly one type of role in the firm.

Different people are suited to different roles: P[i][j] gives the productivity value of the ith person if he works in the jth role in the firm.

However, due to people being employed in different roles, disharmony arises in the firm.

For any two employees i and j, with roles numbered x and y respectively, such that y>x , productivity of the firm decreases by the value D[i][j]*(y-x).

Help the manager of the firm assign roles to employees so that productivity of the firm is maximized.

More formally, for all i, if you assign role R[i] to employee i, productivity of the firm is given by:

sum {P[i][R[i]] for all i} - sum{D[i][j]*(R[j]-R[i]) for all ordered pairs i,j such that R[j] > R[i]}

N,M <= 50

1<=P[i][j] , D[i][j] <= 1e9

Proposed solution: Link