Change-making -- in the U.S. at least -- is trivial because the greedy approximation algorithm works perfectly every time. That particular algorithm works perfectly every time because there isn't the kind of overlap in units of money that you would find in, say, a geometric packing problem.
F'rinstance, for any amount of change to be dispensed, you start with quarters. Add quarters until you can't add any more. Next add dimes. Then nickels. Finish it off with pennies.
That can be done in linear time, because it requires no back-tracking, or recursion.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
no subject
no subject
Change-making -- in the U.S. at least -- is trivial because the greedy approximation algorithm works perfectly every time. That particular algorithm works perfectly every time because there isn't the kind of overlap in units of money that you would find in, say, a geometric packing problem.
F'rinstance, for any amount of change to be dispensed, you start with quarters. Add quarters until you can't add any more. Next add dimes. Then nickels. Finish it off with pennies.
That can be done in linear time, because it requires no back-tracking, or recursion.
(no subject)
(no subject)