Abstract: The issuance and determination of coins will remain stable for a relatively long time. The total amount and denomination of coins is determined by planning and budgeting in a medium and long time. How to determine the denomination of coins so that they can bring convenience to people as much as possible when they are in use? They are not only convenient for calculation, but also can reduce the use frequency as much as possible. This is a practical and useful problem. For a given range and a given coin denomination, with the help of sieve of Eratosthenes method, Dijkstra method, breadth first traversal of graph algorithm, this paper designs a fast calculation of the minimum number of coins for each numerical method which is the least number of coins sieve method to calculate the average amount of coins. For a given range of coins and number of types, for the problem how to determine the optimal combination of coins, this paper presents the process of optimal combination for 3 kinds of coins, and finds out their regularities through the numerical analysis of characteristics of each coin in optimal combination, then fits the curve of optimal combination of each coin denomination by the principle of least squares method. By the fitting curve of limit, this paper greatly reduces the number of traversal to find out the optimal combination of coins.

Key words: optimal combination, dynamic programming, gready algorithm, least square method

摘要： 钱币种类的发行和确定在相对长的一段时间内会保持一定程度的稳定性，钱币的总量和面额是一个国家在中长期通过规划和预算来进行确定的。那么怎么来确定钱币的面额，使得尽可能方便人们使用，不但便于计算，也要尽可能降低使用频率，这是一个比较实际和实用的问题。对于给定范围、给定钱币面额，借助埃拉托色尼筛法、迪杰斯特拉算法、图的广度优先遍历算法思想，设计了一个快速计算每个数值的最小钱币数量方法，即最少钱币数量筛法来计算平均纸张数量；对于给定范围、给定数量的钱币种类如何确定最优钱币组合问题，给出了3种钱币最优组合的寻找过程，即通过分析最优组合中每一个钱币的数值特征，找出其中的规律，并通过最小二乘法原理拟合出最优组合中每个钱币面额的拟合曲线，通过拟合曲线的限制，大大减少寻找最优钱币组合的遍历次数。

关键词: 最优组合, 动态规划, 贪心算法, 最小二乘法