a greedy algorithm is used. At each level of giving back change, the largest possible denomination of either coin or currency is selected. When that denomination can no longer be given, the next largest is used, and so on. This works with the American monetary system, although Weiss makes the point that it is not applicable with all monetary systems.
The fact that this algorithm cannot be used with all monetary systems points up a problem that is not unique to giving change or to greedy algorithms. That is, in evaluating any algorithm, care must be given to the environment in which the algorithm is implemented. Thus, while a greedy algorithm works for the change problem in American currency, it is not guaranteed to work with all currencies. Researchers and evaluators of algorithms should keep in mind that an algorithm used to solve one problem in one environment cannot necessarily be transferred wholesale to a similar problem, even in a similar environment, because of subtle differences that may mask the e
...