We have $N$ queues.
Each of the queues contains a number of numbered ball, and the balls can be taken out in descending order.
For example, the queues can be as the follows:
I want to take $L$ balls from the queues such that the sum of the balls' numbers is as large as possible.
- Let us denote $i$th ball in the queue $q$ by $x_i^q$, e.g., $x_1^2=70$, $x_2^M=1600$.
- Let us denote the number of balls taken from the queue $q$ by $L_q$.
Then, the optimization problem is formulated as $$ \text{maximize}\quad\sum_{q=1}^M\sum_{i=1}^{L_q} x_i^q,\qquad\text{subject to}\quad\sum_{q=1}^M L_q = L, $$ where the decision variables are $L_1, L_2, \ldots, L_q$.
I made a greedy algorithm.
First, set $L_q=0$ for all $q$. Then, select a queue $k$ whose first ball has the largest number. Then, take out a ball from the queue $k$ with updating $L_k$ to $L_k+1$. We repeat these procedures until $L$ balls are taken out from the queues. Finally, $L_1$, $L_2$, $\ldots$, $L_M$ are the solution.
The above algorithm is intuitively supposed to give an optimal solution, but I could've not yet mathematically proved that the output of the algorithm is optimal. Is there any way to prove the above algorithm gives the optimal solution? I am not only an rigorous proof but also very welcome advice on the direction for the proof.
The algorithm is to always choose the largest available number. Prove it by contradiction. Suppose the largest available number is $N,$ and consider any solution $S$ in which $N$ is not chosen. Replace the smallest $s \in S$ by $N$ to get a new solution $S'$. Now $N\ge s$ because $s$ is less than the element $x$ at the head of its queue, and $N\ge x$ so that $\sum S'>= \sum S.$ Either all the elements in $S'$ are equal to $N$ or we have a contradiction. In either, case, we see that an optimal solution must contain $N$.