Prove that the fractional knapsack problem has the greedy-choiceproperty.
Answer
The proof is by induction.To pack a fractional knapsack with asingle item a1,
fill the knapsack to the limit of either the total capacity of theknapsack or
the total quantity of a1 available, whichever is less.
Given a fractional knapsack with total weight capacity W,
and optimally packed with A=a1,a2,…,an, valuesV=v1,v2,…,vn
with weight quantities W=w1,w2,…,wn and a new choice an+1,
value vn+1/wn+1>vi/wi for all i∈1…n and available weightwn+1,
then a new optimal solution can be found as follows.
Let j1 be the index such that vj1/wj1<vi/wj1 for all i∈1…n andi≠j1.
If we replace aj1 with an+1, the objective function
OR
OR