Fractional knapsack; job sequencing with deadlines

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Greedy rule for activity selection? from Lesson 4.2.1
• Strassen exponent? from Lesson 4.1.2
• Selection sort swaps (max)? from Lesson 3.1.1

1 · The Hook

🎣

A thief with a 50 kg bag in a spice shop can scoop part of a sack. Greedy by value per kilogram is optimal. In a jewellery shop, where each item is taken whole or not at all, the same greedy rule can fail badly. GATE tests exactly this contrast, plus a scheduling greedy with deadlines.

2 · Predict First

🤔

Capacity 50. Items (value, weight): (60, 10), (100, 20), (120, 30). If you may take fractions, what is the best value? If items must be whole?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Ratios 6, 5, 4. Fractional: take all of the first two (30 kg, 160) and 20/30 of the third (80): 240. Whole items: greedy by ratio takes the first two (160) and cannot fit the third; the best is items 2 and 3: 220.

Fractional knapsack

Capacity W; item i has value vᵢ and weight wᵢ; any fraction can be taken.

• Sort items by vᵢ / wᵢ descending.

• Take whole items while they fit; take the fitting fraction of the next; stop.

• Optimal (exchange argument: any space used by a lower ratio could hold a higher one).

• Θ(n log n) (sorting).

0/1 knapsack: greedy fails

Items must be taken whole. The predict example: greedy by ratio gets 160, optimal is 220. 0/1 knapsack needs dynamic programming (Lesson 5.1.2).

Job sequencing with deadlines

n jobs, each taking one unit of time, with deadline dᵢ and profit pᵢ (earned only if done by its deadline). Maximise total profit.

• Sort jobs by profit descending.

• For each job, put it in the latest free time slot ≤ its deadline; if none, skip it.

• Optimal; O(n²) simply, O(n log n) with union–find for free slots.

Example: J1 (d 2, p 100), J2 (1, 19), J3 (2, 27), J4 (1, 25), J5 (3, 15). J1 → slot 2; J3 → slot 1; J4 (deadline 1) → slot 1 taken: skip; J2 → skip; J5 → slot 3. Schedule J3, J1, J5: profit 142.

4 · Visual

5 · Worked Examples

Example 1 Easy

Capacity 15; items (value, weight): (25, 5), (40, 10), (30, 6), (20, 4). Fractional knapsack value?

Solution

Ratios 5, 4, 5, 5: take (25, 5), (30, 6), (20, 4) = 15 kg → 75.

Example 2 Medium

Jobs (deadline, profit): a (4, 20), b (1, 10), c (1, 40), d (1, 30). Maximum profit?

Solution

c → slot 1; d → no slot ≤ 1; a → slot 4; b → none. 60.

Example 3 GATE

Jobs J1 (3, 35), J2 (4, 30), J3 (4, 25), J4 (2, 20), J5 (3, 15), J6 (1, 12), J7 (2, 5) (deadline, profit). Maximum profit with unit-time jobs?

Solution

J1 → 3, J2 → 4, J3 → 2, J4 → 1; the rest find no slot. 110.

6 · GATE Traps

⚠️

• Greedy by ratio is optimal only for the fractional knapsack.
• Job sequencing puts each job in the latest free slot, keeping early slots for tighter deadlines.
• Sort jobs by profit, not deadline.
• Fractional knapsack fills the capacity exactly (unless items run out).

7 · Memory Hook

🧠

"Fractions: best ratio first. Deadlines: richest first, as late as allowed."

8 · Connect the Dots

Two greedy problems solved; one shown to need more. Next: Huffman coding, the greedy algorithm that builds optimal prefix codes by repeatedly merging the two rarest symbols.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT2 marksFractional knapsack

Capacity 20; items (value, weight): (30, 5), (40, 10), (45, 15), (77, 22). Fractional knapsack value?

Numerical answer: ________

Q2NAT2 marks0/1 vs fractional

Capacity 50; items (value, weight): (60, 10), (100, 20), (120, 30). Optimal 0/1 knapsack value?

Numerical answer: ________

Q3NAT2 marksJob sequencing

Jobs (deadline, profit): J1 (2, 100), J2 (1, 19), J3 (2, 27), J4 (1, 25), J5 (3, 15). Maximum profit?

Numerical answer: ________

Q4MCQ1 markGreedy failure

For which problem does greedy-by-value/weight NOT guarantee an optimal answer?

• (A) Both
• (B) Fractional knapsack
• (C) Neither
• (D) 0/1 knapsack

Q5NAT2 marksJobs

Jobs (deadline, profit): (2, 50), (2, 40), (1, 30), (3, 20), (3, 10). Maximum profit?

Numerical answer: ________

10 · Rule Card

• Fractional knapsack: sort by v/w; fill greedily; last item fractional; optimal; Θ(n log n).
• 0/1 knapsack: greedy fails → DP.
• Job sequencing (unit jobs): profit descending; latest free slot ≤ deadline; optimal.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

fractional knapsackvalue-to-weight ratio0/1 knapsack greedy counterexamplejob sequencing with deadlineslatest free slot rule

12 · Answer Vault