dsn.umcp-cs%UDel-Relay@sri-unix.UUCP (07/05/83)
From: Dana S. Nau <dsn.umcp-cs@UDel-Relay>
. . . Using coins of value v[1],...,v[n] find a
set of coins for which any amount less than M can
be accumulated and which minimizes the number of
coins over those such sets.
This problem appears similar (although not identical) to the 0/1
Knapsack problem, and thus is probably NP-hard. For approaches to
solving it, I would recommend Branch and Bound (for example, see
Fundamentals of Computer Algorithms, by Horowitz and Sahni).
Dana S. Nau