Canonical Coin Changing and Greedy Solutions
- 1 July 1976
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 23 (3) , 418-422
- https://doi.org/10.1145/321958.321961
Abstract
A natural, and readily computable, first guess at a solution to the coin changing problem is the canonical solution. This solution is a special case of the greedy solution which is a reasonable heuristic guess for the knapsack problem. In this paper, efficient tests are given to determine whether all greedy solutions are optimal with respect to a given set of knapsack objects or coin types. These results improve or extend previous tests given in the literature. Both the incomplete and complete cases are considered.Keywords
This publication has 3 references indexed in Scilit:
- When the Greedy Solution Solves a Class of Knapsack ProblemsOperations Research, 1975
- The Change-Making ProblemJournal of the ACM, 1975
- Algorithmic Solution of the Change-Making ProblemJournal of the ACM, 1970