4 ms·

what about change for 50?

• mcphage 11y ago
  It would be fewer bills than without the $25, but the greedy strategy would still work for both (without, you'd get 3 bills: $20, $20, $10, and that's the optimal). Whereas change for $40, the greedy strategy will give you 3 bills: $25, $10, $5—which is more than the optimal 2 bills.
  • unprepare 11y ago
    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