Definition: An m × n Young tableau is an m × n (m,n∈N) matrix such that the entries of each row are in sorted order from left to right and the entries of each column are in sorted order from top to bottom. Some of the entries of a Young tableau may be ∞ , which we treat as nonexistent elements. Thus, a Young tableau can be used to hold r <= mn finite numbers.
| 2 | 3 | 12 | 14 |
|---|---|---|---|
| 4 | 8 | 16 | ∞ |
| 5 | 9 | ∞ | ∞ |
| ∞ | ∞ | ∞ | ∞ |
Problem:
1.Given m resources and n projects, a profit(i, j) will be obtained if j, 𝟎 ≤ 𝒋 ≤ 𝒎, resources are allocated to project i.
2.Find an allocation of resources to maximize the total profit.