2
$\begingroup$

I have the following problem:

Prove that the fractional knapsack problem has the greedy-choice property.

The greedy choice property should be the following:

An optimal solution to a problem can be obtained by making local best choices at each step of the algorithm.

Now, my proof assumes that there's an optimal solution to the fractional knapsack problem that does not include a greedy choice, and then tries to reach a contradiction.


Proof

Assume there's an optimal solution $A = \{ a_1, a_2, ... , a_n\}$ to the fractional knapsack problem ($F$) that does not include the item $i$, with the greatest value per weight $(\frac{v}{w})$ ratio of all initial items.

Suppose $a_1$ is the item in the solution $A$ with the greatest value per weight ratio. Note that we have $$\frac{v_i}{w_i} \geq \frac{v_{a_1}}{w_{a_1}}$$

Now, suppose we remove $a_1$ from $A$ and we obtain a solution $A'$ to a subproblem $F'$: $$A' = A - a_1$$

If we combine the solution $A'$ (to the subproblem $F'$) with the greedy choice $i$ (or a fraction of it), we will obtain a greater (or equal) valuable solution $B$, since $$\frac{v_i}{w_i} \geq \frac{v_{a_1}}{w_{a_1}}$$

If $B$ is better than $A$, then this is a contradiction, and thus $i$ must be included; if $B = A$, then we have shown that the greedy choice is included anyway, since that would mean that $\frac{v_i}{w_i} = \frac{v_{a_1}}{w_{a_1}}$


Is my proof correct? If not, why, or how can I improve it?

$\endgroup$
  • $\begingroup$ You say that item $i$ has the smallest value per weight ratio and $a1$ has the largest. In that case the inequalities are the reverse of what you wrote. $\endgroup$ – Michael Tiemann Aug 19 '15 at 13:44
  • $\begingroup$ @MichaelTiemann Sorry, for $i$, I meant the item with greatest value per weight ratio (not the smallest) of the original items... $\endgroup$ – nbro Aug 19 '15 at 13:49
  • $\begingroup$ The proof is not very convincing because (1) it does not explain how all the other choices influence the answer, and (2) it does not treat the specific mathematics of the fractional knapsack problem, namely, that at any given point in the construction of the objective function, an infinitesimal (weight) quantity of a suboptimal choice can be replaced by an equal weight quantity of the greedy choice, until the weight quantity of the greedy choice is exhausted. $\endgroup$ – Michael Tiemann Aug 19 '15 at 14:12
  • $\begingroup$ Well, since this problem exhibits optimal substructure, then for your first point my proof should give an answer... not sure if I understood your second point... $\endgroup$ – nbro Aug 19 '15 at 14:16
  • $\begingroup$ Replacing the previously best choice with the newly best choice is not optimal. You want to replace the previously worst choice with the newly best choice to be optimal, as the following answer shows. $\endgroup$ – Michael Tiemann Aug 19 '15 at 14:47
1
$\begingroup$

The proof is by induction.

To pack a fractional knapsack with a single item $a_1$, fill the knapsack to the limit of either the total capacity of the knapsack or the total quantity of $a_1$ available, whichever is less.

Given a fractional knapsack with total weight capacity $W$, and optimally packed with $A = {a_1, a_2, ..., a_n}$, values $V = {v_1, v_2, ..., v_n}$ with weight quantities $W = {w_1, w_2, ..., w_n}$ and a new choice $a_{n+1}$, value $v_{n+1}/w_{n+1} > v_i/w_i$ for all $i \in 1...n$ and available weight $w_{n+1}$, then a new optimal solution can be found as follows. Let $j_1$ be the index such that $v_{j_1} / w_{j_1} < v_i / w_{j_1}$ for all $i \in 1...n$ and $i \neq j_1$. If we replace $a_{j_1}$ with $a_{n+1}$, the objective function improves by $(v_{n+1} - v_{j_1}) / min(w_{n+1},w_{j_1})$. This is the largest possible increase in the objective function because any other replacement choice subtracts a larger amount than $v_{j_1} / min(w_{n+1},w_{j_1})$. We continue this replacement strategy, choosing $j_k$ as the index of the remaining item with the lowest value-to-weight ratio of the remaining items and replacing it entirely with $w_{j_k}$ of $a_i$ or with as much $a_i$ as remains. When the knapsack is completely full of $a_i$ or all available $a_i$ has been placed in the knapsack, we have an optimal solution, achieved by being as greedy as possible with the choice $a_i$.

QED

$\endgroup$

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.