DSA · Grab the biggest coin first: greedy against the exact table
The greedy bet
Grabbing the biggest coin that fits gives the fewest coins with 1, 5, 10 and 25. Does it with any coins?
Two cashiers make the same change. One grabs the biggest coin that still fits and never puts one back; the other fills a table of the fewest coins for every amount first. The panels show both piles, the checks each cashier spent, and the coins greedy wasted.
Board: Algorithm Design Patterns →On a narrow screen the piles stack below the controls.
try this Pick 1, 3, 4 under The coins, set The amount to make to 6, and watch Coins greedy wasted.
Included with a plan
This lab is included with a plan. The first three lessons of every track are free, with their boards and videos. A plan unlocks every lesson, board, video, lab and paper for one price.