0
$\begingroup$

Question: There are $n$ people, labeled $1, 2, . . . , n$ with weights $w_1,w_2,\dots, w_n$ and we are trying to pair as many people up such that there total weights don't exceed $C$.

A greedy algorithm that would result in an optimal solution would be to sort the people by increasing weight and if $n<2$ then return the empty set, otherwise pair the lightest person $l$ with the heaviest person $h$ such that $w_l+w_h\leq C$ and then recursively apply the algorithm to the remaining set of people. If $w_l+w_h\geq C$ then discard $h$ and run the algorithm on the rest of the set.

I am trying to prove that this greedy algorithm finds an optimal set.

Here's my attempt: My attempt for proving this is to apply proof by induction.

Base case: If $n=0$ or $n=1$. Then by our greedy algorithm it would return an empty set, which is the optimal solution.

Inductive step: Suppose $n\geq2$ and that $w_1\leq w_2 \leq \dots w_n$. There there are two cases to consider.

Case 1: When the lightest person and heaviest person have a combined weight exceeding $C$. i.e $$w_1+w_n > C$$

Proof. We know that for every $i$, $1 \leq i \leq n$, $w_i \geq w_1$ (because we ordered them by increasing weight). And so we have $$w_i+w_n \geq w_1+w_n \geq C$$ This tells us that the optimal set doesn't contain $w_n$. Thus, our algorithm would return the optimal set among the people $1, 2, . . . , n−1$

Case 2: When the lightest person and heaviest person have a combined weight less than or equal to $C$. i.e $$w_1+w_n \leq C$$

This is the part I don't know how to prove and was wondering is someone could lead me in the right direction for this part of the proof.

$\endgroup$
1
$\begingroup$

For case 2: You know that your algorithm give you the optimal set among the people $2,...,n−1$ plus the pair $(1,n)$

Consider an optimal set for $1,...,n$. We can assume, without loss of generality, that it contains $1$ (otherwise just replace any people by $1$ and you still have an optimal set). Moreover you can assume, without loss of generality, that it contains $n$ (otherwise just replace the people paired with $1$ by $n$ and you still have an optimal set).

Now two cases: Either the optimal set contains the pair $(1,n)$. In this case you know that your algorithm return the optimal set for $2,...,n-1$ and the pair $(1,n)$ thus return an optimal set.

Or the optimal set contains does not contain the pair $(1,n)$. Let $i,j$ be such that it contain $(1,i)$ and $(j,n)$. You can remark that the set where you remove those two pairs and ad the pair $(1,n)$ and $(i,j)$ is also an optimal set (since $w_i<w_n$ and $w_j<C-w_n$). Thus you are back to the first case.

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