Items: 1 (10 kg, Rs 60), 2 (7 kg, Rs 28), 3 (4 kg, Rs 20), 4 (2 kg, Rs 24). Total weight limit = 11

Q: What is GATE-CS?

GATE-CS is a competitive examination conducted in India. This question is from the 2018 GATE-CS Algorithm paper.

Q: How can I prepare for GATE-CS Algorithm?

To prepare for GATE-CS Algorithm, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2018 question covers Greedy Algorithms topic.

Q: What is the difficulty level of this question?

This GATE-CS 2018 Algorithm question has a medium difficulty level and is marked as an important question.

Q: Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

Question

Items: 1 (10 kg, Rs 60), 2 (7 kg, Rs 28), 3 (4 kg, Rs 20), 4 (2 kg, Rs 24). Total weight limit = 11 kg. Splitting is not allowed (0-1 knapsack). Let V_opt be the value obtained by the optimal algorithm and V_greedy be the value obtained by the greedy algorithm that sorts by value-to-weight ratio (descending) and packs greedily without splitting. The value of V_opt − V_greedy is _____.

Accepted Answer

Correct Answer: 16Step-by-step Solution:Value-to-weight ratios: Item 1: 60/10 = 6; Item 2: 28/7 = 4; Item 3: 20/4 = 5; Item 4: 24/2 = 12. Sorted descending by ratio: Item 4 (12), Item 1 (6), Item 3 (5), Item 2 (4).Greedy algorithm:Take Item 4: weight = 2, value = 24. Remaining capacity = 9 kg.Try Item 1: weight = 10 > 9. Skip.Take Item 3: weight = 4, value = 20. Remaining capacity = 5 kg.Try Item 2: weight = 7 > 5. Skip.V_greedy = 24 + 20 = Rs 44.Optimal algorithm (by exhaustive search):Try Item 1 alone: 10 kg, Rs 60. Remaining 1 kg — no item fits. Value = 60.Try Item 2 + Item 4: 9 kg, Rs 52. Remaining 2 kg — Item 4 already taken; Item 3 (4 kg) too heavy. Value = 52.Try Item 3 + Item 4: 6 kg, Rs 44. Remaining 5 kg — Item 2 (7 kg) too heavy. Value = 44.Try Item 1 + any: 10 + any ≥ 12 > 11. No combination with Item 1 and anything else.V_opt = 60 (Item 1 alone).V_opt − V_greedy = 60 − 44 = 16.Key Concept: The greedy algorithm for the fractional knapsack problem does not give the optimal solution for the 0-1 knapsack problem. Here, the greedy algorithm skips Item 1 (weight 10, value 60) because its weight exceeds the remaining capacity after taking Item 4. However, Item 1 alone fills 10 of the 11 kg capacity and provides Rs 60, which is Rs 16 more than the greedy result of Rs 44. This illustrates why the 0-1 knapsack requires dynamic programming for an optimal solution.

Master GATE-CS with Our Test Series

More Questions from Greedy Algorithms

Frequently Asked Questions

Master GATE-CS with Our Test Series

More Questions from Greedy Algorithms

Frequently Asked Questions