This paper analyzes a necessary and sufficient condition for the change-making problem to be solvable with a greedy algorithm. The change-making problem is to minimize the number of coins used to pay a given value in a specified currency system. This problem is NP-hard, and therefore the greedy algorithm does not always yield an optimal solution. Yet for almost all real currency systems, the greedy algorithm outputs an optimal solution. A currency system for which the greedy algorithm returns an optimal solution for any value of payment is called a canonical system. Canonical systems with at most five types of coins have been characterized in previous studies. In this paper, we give characterization of canonical systems with six types of coins, and we propose a partial generalization of characterization of canonical systems.
翻译:本文分析一个必要和充分的条件,使变革问题与贪婪的算法能够溶解。 改变问题在于尽量减少在特定货币体系中用于支付特定价值的硬币数量。 这个问题是NP硬性的,因此贪婪的算法并不总是产生最佳的解决方案。 然而,对于几乎所有实际货币体系来说,贪婪的算法产出了一个最佳解决方案。 贪婪的算法返回任何支付价值的最佳解决方案的货币体系被称为“骗人体系 ” 。 以往的研究已经对最多五类硬币的公币体系进行了定性。 在本文中,我们对六类硬币的金币体系进行了定性,我们建议部分地概括对金币体系的定性。