Hamilton to stay on $10; Tubman replacing Jackson

Re:Hamilton to stay on $10; Tubman replacing Jackson by mcphage on Wednesday April 20, 2016 @04:43PM (#11537591)

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.

[ Parent | on HN ]

Re:Hamilton to stay on $10; Tubman replacing Jackson by unprepare on Thursday April 21, 2016 @07:12AM (#11541065)

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?

[ Parent | on HN ]

Re:Hamilton to stay on $10; Tubman replacing Jackson by mcphage on Thursday April 21, 2016 @08:40AM (#11541592)

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

[ Parent | on HN ]