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

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