Lemonade - The Idea

When a customer pays $20, you need to give$15 change. You have two options:

$1.$ One $10 and one$5

$2.$ Three $5 bills Which is better? Always prefer option 1 (use a$10). Why? The $5 bill is more versatile. It can make change for$10 customers. The $10 bill can only help with$20 customers. Save the flexible currency. Here's greedy: use the least flexible bills first. This "save the flexible resource" pattern shows up in many greedy problems. When multiple choices work, pick the one that preserves your options.