0
$\begingroup$

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: Queue_Fig

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.

$\endgroup$
  • $\begingroup$ Suppose queue 1 has 5,10, queue 2 has 1, 1000 and L=2. If I understand your algorithm correctly, it chooses 5,10 instead of 1,1000. $\endgroup$ – saulspatz Mar 21 '18 at 16:39
  • $\begingroup$ @saulspatz Supposing that a queue 1 has two balls with number 5 and 10, and a queue 2 has also two balls with number 1 and 1000. If we have to take out only two balls, then the optimal solution will be $L_1=1$ and $L_2=1$. Then, the objective value becomes $10+1000=1010$. (Algorithm also gives $L_1=L_2=1$.) $\endgroup$ – Danny_Kim Mar 21 '18 at 16:43
  • $\begingroup$ Okay, I had it backwards. Your algorithm is simply to always take the largest available ball, and it clearly works. $\endgroup$ – saulspatz Mar 21 '18 at 16:56
  • $\begingroup$ @saulspatz Yeah, I just wanna prove its optimality rigorously and mathematically. $\endgroup$ – Danny_Kim Mar 21 '18 at 16:57
  • $\begingroup$ I still don't understand how your algorithm doesn't output $L_1=2$ and $L_2=0$ in @saulspatz 's example. $\endgroup$ – Rchn Mar 21 '18 at 17:18
0
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.