Canonical Coin Systems for Change-Making Problems

Details Canonical Coin Systems for Change-Making Problems Canonical Coin Systems for Change-Making Problems

2008-09-02

arxiv.org/abs/0809.0400v2

Computer Science

Data Structures and Algorithms

7 pages

Scientific paper

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, in most 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 \emph{canonical} coin systems with four or five types of coins, and a sufficient condition for non-canonical coin systems, respectively. Moreover, we present an $O(m^2)$ algorithm that decides whether a tight coin system is canonical.

Affiliated with

Also associated with

No associations

Rating

Canonical Coin Systems for Change-Making Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Canonical Coin Systems for Change-Making Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Canonical Coin Systems for Change-Making Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-60993