In 0/1 Knapsack problem we want to maximize the profit subject to the total weig
ID: 642164 • Letter: I
Question
In 0/1 Knapsack problem we want to maximize the profit subject to the total weight <= M.
M = 20
(w1, w2, w3) = (18, 15, 10)
(p1, p2, p3) = (25, 24, 15)
(a) One greedy strategy is: consider the objects in order of non-increasing density Pi/Wi; add the object into the knapsack if it fits. show that this strategy doesn't necessarily yield optimal solutions.
(b) One greedy strategy is: consider the objects in order of non-decreasing density Pi/Wi; add the object into the knapsack if it fits. show that this strategy doesn't necessarily yield optimal solutions.
Explanation / Answer
n 0/1 Knapsack problem we want to maximize the profit subject to the total weight <= M.
M = 20
(w1, w2, w3) = (18, 15, 10)
(p1, p2, p3) = (25, 24, 15)
(a) One greedy strategy is: consider the objects in order of non-increasing density Pi/Wi; add the object into the knapsack if it fits. show that this strategy doesn't necessarily yield optimal solutions.
(b) One greedy strategy is: consider the objects in order of non-decreasing density Pi/Wi; add the object into the knapsack if it fits. show that this strategy doesn't necessarily yield optimal solutions.
Solution is same for both of them:
P1/W1=25/18=1.389
P2/W2=24/15= 1.6
P3/W3=15/10= 1.5
M=20
kp2, kp3, kp1
Weight contribution 15 , 0 , 0
Profit contribution 24 , 0 , 0 =24
24*(15/15) =24 (remaining 5 goes waste)
kp1, kp3, kp2
Weight contribution 18 , 0 , 0
Profit contribution 25 , 0 , 0 =25
25*(18/18)=25 (remaining 2 goes waste)
Reason:
Consider a solution with non-increasing density Pi/Wi and we can add part of weight
kp2, kp3, kp1
Weight contribution 15 , 5 , 0
Profit contribution 24 , 7.5 , 0 =24+7.5=31.5(optimal solution)(and bag is full)
24*(15/15) =24 5*(15/10)=7.5