3 ms·
Adding $25 USD bills would break the greedy choice property for making change. Making $40 in change using a greedy strategy would mean selecting a 25, a 10, and
by gradys 10y ago
Adding $25 USD bills would break the greedy choice property for making change. Making $40 in change using a greedy strategy would mean selecting a 25, a 10, and a 5, while the optimal choice is to select two 20s.
- unprepare 10y agowhat about change for 50?
- mcphage 10y agoIt 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 10y agochange 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 10y agoIt'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
- dkuntz2 10y agoGiven that we don't have $40 bills, I'm not sure this is a problem.