Fractional knapsack problem is a famous problem in greedy algorithms. The problem statement tells that a knapsack is given which has a weight W. You are given a list of weights and values of different items. The expected output is to output the maximum value of items that can be packed inside the knapsack.
ALGORITHM
1.We find the value per unit weight for each item
2.Next, we find the item with the maximum value per unit weight and check if the weight of that item is less or equal to the resultant weight of the knapsack then we include that item completely. Then we update the resultant weight of the knapsack.
3.If the weight of the item is less than that of the knapsack but the weight of the knapsack is not zero, then we include that amount of the item which fits into the knapsack.
4.If the sum of weights of all the items is less than the weight of the knapsack, then the output will be the sum of the values of each item.
CODE
The code snippet is:
Hope this helps you! If you liked the article do follow me on Github!
Top comments (0)