krishpatel2383

[krishpatel2383]

the fractional knapsack problem is that given the weights and values of N items and we have to put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In the 0-1 Knapsack problem, we are not allowed to break items. We either take the whole item or don’t take it. but In Fractional Knapsack, we can break items for maximizing the total value of the knapsack.

Solution using Greedy Approach: The idea of the greedy approach is to calculate the ratio value/weight for each item and sort the item on the basis of this ratio. Then take the item with the highest ratio and add them until we can’t add the next item as a whole and at the end add the next item as much as we can. Which will always be the optimal solution to this problem.