0
$\begingroup$

Given n numbers find the way to assign them to blocks of 3 (and possible one block of 1 or 2 if n is not divisible by 3) so that sum of smallest elements from each full block is maximal.

ie. numbers 400, 350, 300, 250, 200, 150, 100, can be divided into [400, 350, 300], [250, 200, 150], [100] with above mention sum of 450.

I know that correct approach is just to assign numbers to block in sorted order(so first block contains first, second and third largest element and so on), but i can't find a way to prove it correctness.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

We sort all the blocks according to the descending order of their minimal elements. We name the blocks $B_1, B_2, \dots$ in that order.

For every $i\geq 1$, let $m_i$ be the smallest element of $B_i$. Thus $m_j \geq m_i$ whenever $j \leq i$.

For any $1 \leq j \leq i$ and any element $x \in B_j$, we know that $x \geq m_j \geq m_i$.

This means that, for any $i$, there are at least $3i$ elements (i.e. all elements from $B_1$ to $B_i$) larger than (or equal to) $m_i$.

In other words, if we sort the original $n$ numbers in descending order as $x_1, x_2, \dots$, then we must have $m_i \leq x_{3i}$.

Adding everything together, we see that the sum $m_1 + m_2 + \dots$ is at most $x_3 + x_6 + \dots$.

On the other hand, this upper bound can be achieved simply with the greedy algorithm: group them as $\{x_1, x_2, x_3\}$, $\{x_4, x_5, x_6\}$, etc.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.