Project ForgeConsider the weights and values of items listed below. There is only one unit of each item.
Item 1: Weight 10 Kgs, Value 60 Rupees Item 2: Weight 7 Kgs, Value 28 Rupees Item 3: Weight 4 Kgs, Value 20 Rupees Item 4: Weight 2 Kgs, Value 24 Rupees
The task is to pick a subset of these items such that their total weight is no more than 11 Kgs and their total value is maximized (no item may be split). Vopt is the value from an optimal (0/1 knapsack) algorithm. A greedy algorithm sorts items by value-to-weight ratio descending and packs them greedily, skipping any item that doesn't fit. Vgreedy is the total value from the greedy algorithm. The value of Vopt − Vgreedy is ____.
Explanation
Vopt: checking all feasible combinations within 11 Kg, item 1 alone (weight 10, value 60) beats every other combination (item2+item4=52, item2+item3=48, item3+item4=44) — Vopt=60. Vgreedy: ratios are item4=12, item1=6, item3=5, item2=4 (descending order item4,item1,item3,item2). Greedy takes item4 (w2,fits,cap9 left), skips item1 (w10>9), takes item3 (w4≤9,cap5 left,value 24+20=44), skips item2 (w7>5). Vgreedy=44. Vopt−Vgreedy = 60−44 = 16.
Source: GATE CS 2018 (2018)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.