Applied Test Series

Question

Consider the following items with their associated weights and values.
 

If a knapsack of capacity 25 units of weight is available and we are allowed to take either the item completely or leave it the maximum possible profit if we follow the greedy approach by being greedy about profit is _____

Answer 1

As in question it is asked to use greedy approach, hence we will first calculate profit per unit  (Value / weight )

Item	Value / Weight
1	11
2	2.57
3	3.4
4	4.33
5	2.7
6	8
7	12

Now we have to select items in decreasing order of value per unit such that they doesn’t exceed the max capacity of 25 unit.

Items we choose are ITEM7 (1kg) + ITEM1 (2kg) + ITEM6(2kg) + ITEM4(3kg) + ITEM3(5kg) + ITEM5(10kg)

Maximum possible weight= 23kg

Maximum possible profit = 107