The algorithm to solve the fractional knapsack problem is a little different from the dynamic programming version. While, in the 0-1 knapsack problem, we can only use the whole item to fill the knapsack, in the fractional knapsack problem, we can use fractions of the items. Let's use the same example we used before to compare the differences, as follows:
Item # | Weight | Value |
1 | 2 | 3 |
2 | 3 | 4 |
3 | 4 | 5 |
In the dynamic programming example, we considered that the knapsack could only carry a weight of 5. For this example, we can say that the best solution would be filling the knapsack with items 1 and 2, which together have a weight of 5 and a total value of 7.
If we consider the same capacity for the fractional ...