1. [10 marks] In class, we learned that for the fractional knapsack problem, the
ID: 3593689 • Letter: 1
Question
1. [10 marks] In class, we learned that for the fractional knapsack problem, the greedy strategy of selecting the item with the highest value to weight ratio first will always yield an optimal solution. Now construct counterexamples for the following two greedy strategies, to show that they will not always produce an optimal solution to the fraction knapsack problem In your solution, provide are indeed counterexamples. sufficient details to show what you constructed (a) [5 marks] Always select the most valuable item first. (b) [5 marks] Always select the lightest item first.Explanation / Answer
Consider 3 items and their weights are w = { 16.7,16.1,10 }
their values/profits are = {25,24,15}
Capacity of knapsack is = 20
Now if we are greedy about highest value/weight then
v1/w1 = 25/16.7 = 1.497 , v2/w2 = 24/16.1 = 1.49 , v3/w3 = 15/10 = 1.5 (highest)
Total value is = 25 * 0 + 24 * 10/16.1 + 15 * 1 = 29.9
(a)
Now if we are greedy about most valuable item then
Total value is = 25 * 1 + 24 * 3.3 /16.1 + 15 * 0 = 29.92
Consider 3 items and their weights are w = { 10.011,10.01,10 }
their values/profits are = {30.03301,30.05,30}
Capacity of knapsack is = 20
Now if we are greedy about highest value/weight then
v1/w1 = 30.03301/10.011 = 3.0000001 , v2/w2 = 30.05/10.01 = 3.002 (highest) , v3/w3 = 30/10 = 3
Total value is = 30.03301 * 9.99/10.011 + 30.05 * 1 + 30 * 0 = 60.019
(b)
Now if we are greedy about most lightest item then
Total value is = 30.03301 * 0 + 30.05 * 10/10.01 + 30 * 1 = 60.02
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.