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.


If $g_1$ is included in $O$, then we are done.
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'$.
$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.
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.)