Title :
Canonical Coin Systems for CHANGE-MAKING Problems
Author_Institution :
Dept. of Comput. Sci. & Eng., Shanghai Jiao Tong Univ., Shanghai, China
Abstract :
The change-making problem is to represent a given value with the fewest coins under a given coin system. As a variation of the knapsack problem, it is known to be NP-hard. Nevertheless, inmost real money systems, the greedy algorithm yields optimal solutions. In this paper, we study what type of coin systems that guarantee the optimality of the greedy algorithm. We provide new proofs for a sufficient and necessary condition for the so-called canonical coin systems with 4 or 5 types of coins, and a sufficient condition for non-canonical coin systems, respectively.Moreover, we propose an O(m2) algorithm that decides whether a tight coin system is canonical.
Keywords :
combinatorial mathematics; computational complexity; greedy algorithms; integer programming; knapsack problems; NP-hard problem; canonical coin system; change-making problem; combinatorial optimization; greedy algorithm; integer programming problem; knapsack problem; optimal solution; real money system; Application software; Computer network management; Computer science; Dynamic programming; Greedy algorithms; Hybrid intelligent systems; Laboratories; Linear programming; Nickel; Polynomials; Change-Making problems; canonical coin systems; combinatorial problems;
Conference_Titel :
Hybrid Intelligent Systems, 2009. HIS '09. Ninth International Conference on
Conference_Location :
Shenyang
Print_ISBN :
978-0-7695-3745-0
DOI :
10.1109/HIS.2009.103
