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

migrated from cstheory.stackexchange.com Aug 2 '13 at 9:03

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 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
1
$\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$
  • $\begingroup$ This does not prove that at each step we make a greedy choice which results in a global optimal solution. Your proof should be complete. $\endgroup$ – nbro Sep 3 '15 at 14:27
  • $\begingroup$ @Axl, that's not relevant to the question. There's no need to prove that. My proof is already complete. The question says: I have already proven that $O'$ is at least as good as the optimal solution $O$; does this guarantee that $O'$ will be an optimal solution, too? We don't need to know anything about greedy or how $O$ or $O'$ was constructed to answer that question. If you think I've missed something, feel free to elaborate! $\endgroup$ – D.W. Sep 3 '15 at 16:40
  • $\begingroup$ The title says "Proving greedy choice property of fractional knapsack", and if the proof provided by the OP is not completely clear, IMO, it would be nice to have an answer with a complete exhaustive proof. I think that the confusion is due to the fact that the OP did not think that $g1$ is the item with the best value/weight ratio... $\endgroup$ – nbro Sep 3 '15 at 17:23
  • $\begingroup$ @Axl, The question is stated in the body of the question. To quote, the question is: "How does [the above proof] show that $O'$ is also an optimal solution [...]?" My answer explains how it shows that $O'$ is also an optimal solution. Yes, the question includes all sorts of other details that turn out not to be necessary, but that's because the asker didn't know what the answer would be. I still think my answer is valid, but I encourage you to write your own answer if you think you can provide a different and useful perspective! $\endgroup$ – D.W. Sep 3 '15 at 17:26

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.