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$ bethegreedysolution,wherethe itemsareorderedaccordingto thegreedychoices.Weneed toshowthatthereexistssomeoptimalsolution$O'$thatincludesthechoice $g_1$.CASE1:$g_1$isnon-fractional.If$g_1$isincludedin $O$,thenwearedone.If$g_1$isnotincludedin$O$,thenwearbitrarilyremove$w_{g_1}$worthofstuff from$O$andreplaceitwith$g_1$toproduce$O'$.$O'$ isasolution, anditis atleastasgood 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.
Proving greedy choice property of fractional knapsack
algorithms;algorithm analysis;correctness proof;greedy algorithms