₹600, plenty of notes, and a greedy ATM gets stuck

transcript

Ask this ATM for 600 rupees. It has the notes. And a greedy planner still gets stuck. Watch why.

It has 500 rupee notes. It has 200 rupee notes. But the 100 rupee cassette is empty.

Greedy grabs the biggest note first. One 500 fits. That leaves 100 rupees to make. No 100s loaded. Stuck.

But here's the thing. Three 200s make 600. Greedy never goes back to look. It just gives up.

Plain greedy: the most 500s, then stuck. The fix: if the rest can't be made, take one fewer. One fewer 500 is zero. Then three 200s. Done.

Asha takes 2,600: four 500s and three 200s. Then 600: three 200s. Backtracking at work. 250? Rejected at the ATM. The bank never sees it.

Plan from the notes actually loaded. Three note types, a 10,000 rupee cap. A few thousand steps at most. And the plan comes before the debit. Never after.

Full breakdown in the lecture.