Prove that The Fractional Knapsack Greedy Algorithm always p

Prove that The Fractional Knapsack Greedy Algorithm always produces a load that maximizes profit.

Solution

The Fractional Knapsack Greedy Algorithm allows you to use the fraction of an item as compared to (0-1) knapsack problem which always provides a load value that will maximize the profit.

Let us understand the problem with the help of an example

The weight that can be taken maximum is 4 pounds

Item A -> weight 2 pounds -> Rate 100$

Item B -> weight 1 pound -> Rate 10$

Item C -> weight 3 pound -> Rate 120$

The person wants to maximize the amount by taking the weight of 4 pounds

Using (0-1) Knapsack

Answer will be C + B = 120 + 10 = 130$

But the fractional Knapsack will give the answer

Answer will be C + A/2 = 120 + 100/2 = 170$

Hence the Fractional Knapsack Greedy Algorithm always produces a load that maximizes profit. since it depends on cost/weight and not only cost