Consider a $m \times n$ Matrix.
Every column represents a class and every row an observation. Every row/observation is a probability distribution, hence every row sums up to 1.
We now want to choose elements $a_{i,j}$ of the Matrix.
For every column $k_j$ elements have to be chosen, but we can choose just one element per row. The sum of the chosen elements have to be maximized.
I guess this problem is NP-hard. I didn't found an efficient solution. To prove that, I want to find a reduction from a NP-hard problem to my problem.
Hopefully someone has an idea for a reduction (or an efficient algorithm).