# Proving greedy choice property of fractional knapsack

A typical way of proving the greedy choice property of the fractional knapsack problem is as follows:

From Slide 5 of this link:

Given: A set of items $I = \{I_1,I_2..I_n\}$ with weights $\{w_1,w_2 ... w_n\}$ and values $\{v_1,v_2 ...v_n\}$. Let $P$ be the problem of selecting items from $I$, with the weight limit $K$ such that the resulting value is maximum.

Let $O = \{o_1,o_2 ... o_j\} \subseteq I$ be the optimum solution of problem $P$.

Let $G = \{g_1,g_2 ... g_k\} \subseteq I$ be the greedy solution, where the  items are ordered according to the greedy choices.

We need to show that there exists some optimal solution $O'$ that includes the choice $g_1$ .

CASE 1: $g_1$ is non-­fractional.

1. If $g_1$ is included in $O$, then we are done.
2. If $g_1$ is not included in $O$, then we arbitrarily remove $w_{g_1}$ worth of stuff from $O$ and replace it with $g_1$ to produce $O'$.
3. $O'$ is a solution, and it is at least as good as $O$.

In the above proof, step $3$ for CASE 1 merely shows that weight criteria is satisfied. How does it show that $O'$ is also an optimal solution(i.e. in terms of value achieved), more so when we are "arbitrarily removing $w_{g_1}$ worth of stuff" without paying attention to corresponding change in value ?

UPDATE: I found the answer in terms of change in value here. I am not sure if this should go into the answer part. Mods, please suggest.

• You should answer your own question with your newly-found information. – Yuval Filmus Aug 2 '13 at 12:08
• Answering your own question is totally fine. – Juho Aug 2 '13 at 13:51

## 1 Answer

Remember that $O$ is assumed to be an optimal solution. If $O'$ is a solution that is at least as good as $O$, then $O'$ has to be optimal too.

In particular, since $O$ is optimal, $O'$ cannot be better than $O$; so $O'$ must be exactly as good as $O$. Since there's nothing better than $O$, and since $O$ and $O'$ have the same goodness, there can't be anything better than $O'$ either. Consequently, $O'$ is also optimal: both $O$ and $O'$ are optimal solutions. (There can be more than one optimal solution.)