|
|
|
|
|
|
by eddington
5141 days ago
|
|
|
I don't know why you're saying it isn't NP-complete. For an arbitrary set of coins, it's definitely NP-complete. You could easily reduce 0-1 ILP to it, or subset-sum. If you don't believe me, believe http://graal.ens-lyon.fr/~abenoit/algo09/coins2.pdf "Optimally making change—representing a given value with the fewest coins from a set of denominations—is in general NP-hard." |
|
|