Canonical Coin Systems for CHANGE-MAKING Problems

摘要：

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 suf cient and necessary condition for the so-called canonical coin systems with 4 or 5 types of coins, and a suf cient condition for non-canonical coin systems, respectively. Moreover, we propose an O(m2) algorithm that decides whether a tight coin system is canonical.

关键词： CHANGE-MAKING problems canonical coin systems combinatorial problems

作者: Xuan Cai

作者单位: Department of Computer Science and Engineering, Shanghai Jiao Tong University BASICS, MOE-Microsoft Laboratory for Intelligent Computing and Intelligent Systems Shanghai 200240, China

会议类型: 国际会议

会议名称: 2009 Ninth International Conference on Hybrid Intelligent Systems(第九届混合智能系统国际会议 HIS 2009)

会议地点: 沈阳

会议语种:英文

页码: 1-6

在线出版日期: 2009-08-12（万方平台首次上网日期，不代表论文的发表时间）