1
$\begingroup$

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.

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

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.)

$\endgroup$
0

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.