3 ms·

change of 50 in two bills and change of 40 in three, is less optimal than change of 50 in three and 40 in two?

• 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