3 ms·
It's not about comparing the number of bills vs. each other—it's not surprising that adding an additional denomination lets you make change in fewer bills. It'
by mcphage 11y ago
It's not about comparing the number of bills vs. each other—it's not surprising that adding an additional denomination lets you make change in fewer bills. It's about whether the greedy algorithm for making change gets you the optimum number. Currently it does, but if you add a $25 bill, it would not.
Currently:
$40:
greedy: $20, $20
optimal: $20, $20
is greedy optimal: Yes
$50:
greedy: $20, $20, $10
optimal: $20, $20, $10
is greedy optimal: Yes
Including a $25 bill:
$40:
greedy: $25, $10, $5
optimal: $20, $20
is greedy optimal: No
$50:
greedy: $25, $25
optimal: $25, $25
is greedy optimal: Yes