Given the weights and values of n items, the task is to put these items in a knapsack of capacity w to get the maximum total value in the knapsack.
Note: Unlike the 0/1 knapsack, you are allowed to break the item.
Input: items[] = {{value: 60, weight: 10}, {value:100, weight: 20}, {value:120, weight: 30}}, w = 50
Output: 240.0
Input: items[] = {{value: 500, weight: 30}}, w = 10
Output: 66.667
Solutions
Method 1: Greedy
In the greedy approach, we calculate the ratio of value to weight and sort the items in descending order of this ratio.
Next, start adding the items to the knapsack.
Add the whole item if the current weight is less than the capacity; else, add a portion of the item to the knapsack.
Stop when all the items have been considered or the capacity of the knapsack is exhausted.
Complexity
The time complexity of this solution is O(nlogn) and space complexity is O(n).