There
are *n* items in a store. For i =1,2, . . . , n, item i has weight
*w _{i }*> 0
and worth

In Symbol, the fraction knapsack problem can be stated as follows.

maximize ^{n}**S**_{i=1 }*x _{i}v_{i} *
subject to constraint

It is clear that an optimal solution must fill the knapsack exactly, for
otherwise we could add a fraction of one of the remaining objects and increase
the value of the load. Thus in an optimal solution ^{n}**S**_{i=1
}*x _{i}w_{i} = W.*

**Greedy-fractional-knapsack ( w, v, W)**

FOR

i=1 ton

dox[i] =0

weight = 0

while weight <W

doi= best remaining item

IF weight +w[i] ≤W

thenx[i] = 1

weight = weight +w[i]

else

x[i] = (w- weight) /w[i]

weight =W

returnx

**Analysis **

If the items are already sorted into decreasing order of
*v _{i }/ w_{i,
}*then

the while-loop takes a time in

Therefore, the total time including the sort is in

If we keep the items in heap with largest *
v _{i}/w_{i
}*at
the root. Then

- creating the heap takes
*O(n)*time - while-loop now takes
*O(log n)*time (since heap property must be restored after the removal of root)

Although this data structure does not alter the worst-case, it may be faster if only a small number of items are need to fill the knapsack.

One variant of the 0-1 knapsack problem is when order of items are sorted by increasing weight is the same as their order when sorted by decreasing value.

The optimal solution to this problem is to sort by the value of the item in decreasing order. Then pick up the most valuable item which also has a least weight. First, if its weight is less than the total weight that can be carried. Then deduct the total weight that can be carried by the weight of the item just pick. The second item to pick is the most valuable item among those remaining. Keep follow the same strategy until thief cannot carry more item (due to weight).

**Proof**

** **One way to proof the correctness of the above algorithm is to
prove the greedy choice property and optimal substructure property. It consist
of two steps. First, prove that there exists an optimal solution begins with the
greedy choice given above. The second part prove that if
*A *is an optimal
solution to the original problem *S*, then
*A - a* is also an optimal
solution to the problem *S - s* where
*a* is the item thief picked as in
the greedy choice and *S - s* is the subproblem after the first greedy choice
has been made. The second part is easy to prove since the more valuable items
have less weight.

Note that if *v` / w` _{ }
*, is not it can replace any other because

**Theorem ***
The fractional knapsack problem has the greedy-choice
property.*

* Proof
*Let the ratio