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?
Best Answer
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