3 ms·
>making change out of your pocket is still solving the subset-sum problem in your head, which is of course NP-complete. Generally speaking, that's true. Most c
by xyzzyz 16y ago
>making change out of your pocket is still solving the subset-sum problem in your head, which is of course NP-complete.
Generally speaking, that's true. Most currencies however are designed, so that the greedy algorithm always works and produces optimal solution. The coin systems given in the linked article do not have this property, so they are actually inferior to real systems.
edit: come to think of it, they in fact do, but it requires ridiculous amounts of pennies, so my argument still holds.
- Locke1689 16y agoFWIW I got that from the original poster: the general case problem is NP complete but most of our special cases are not.