The question is how to trace a Knapsack problem with greedy algorithm using the following information?
P=[10,7,12,13,6,20]
W=[3,2,4,3,13,8]
M=15
n=6
I'd appreciate it if some one could help me understand this or point me to the right direction.
Well, if it's 'fractional knapsack' (i.e. you can take fractions of the items) then it's easy:
The items are (as price, weight pairs) [(10, 3), (7, 2), (12, 4), (13, 3), (6, 13), (20, 8)]
Intuitively, you'll want to get an item first which will provide more price with less weight. So, let's sort the items by their price to weight ratio:
[(13, 3), (7, 2), (10, 3), (12, 4), (20, 8), (6, 13)]
Now, until you run out of capacity or an item, take the most valuable item as much as you can.
0. cap = 15, price = 0
1. Take (13, 3): cap = 12, price = 13
2. Take (7, 2): cap = 10, price = 20
3. Take (10, 3): cap = 7, price = 30
4. Take (12, 4): cap = 3, price = 42
5. Take (20, 8): cap = 0, price = 49.5
[in this step, you have capacity to take 3 units, so take 3 units of the 5th item, the price of which is 3*20/8]
If you cannot take fractional items, then such a greedy approach may not give you the optimal solution.