硬币变化：贪婪的方法 [英] Coin Change : Greedy Approach

问题描述

问题在于，使用四分之一硬币，硬币，镍币和几美分硬币来改变n美分，并且使用最少的硬币总数。在四种面额分别为四分之一，二美分，镍和几美分的特殊情况下，我们的c1 = 25，c2 = 10，c3 = 5和c4 =1。

The Problem is making n cents change with quarters, dimes, nickels, and pennies, and using the least total number of coins. In the particular case where the four denominations are quarters,dimes, nickels, and pennies, we have c1 = 25, c2 = 10, c3 = 5, and c4 = 1.

如果我们仅使用四分之一硬币，一角硬币和几分钱（没有镍币），则
的贪婪算法将使用六个硬币对 30美分进行更改 （一个四分之一硬币和五个便士），而我们本可以使用三个硬币，即三个角钱。

If we have only quarters, dimes, and pennies (and no nickels) to use, the greedy algorithm would make change for 30 cents using six coins—a quarter and five pennies—whereas we could have used three coins, namely, three dimes.

给出一组面额，如何我们说贪婪的方法是否可以创建最佳解决方案？

Given a set of denominations, how can we say whether greedy approach creates an optimal solution?

推荐答案

您要问的是如何确定给定硬币系统是否为规范以解决变更问题。如果贪心算法总是给出最优解，则系统是标准的。您可以通过有限的步骤来确定一个包含1美分硬币的硬币系统是否规范。详细信息以及某些情况下更有效的算法可在 http://arxiv.org/pdf/0809.0400中找到.pdf 。

What you are asking is how to decide whether a given system of coins is canonical for the change-making problem. A system is canonical if the greedy algorithm always gives an optimal solution. You can decide whether a system of coins which includes a 1-cent piece is canonical or not in a finite number of steps. Details, and more efficient algorithms in certain cases, can be found in http://arxiv.org/pdf/0809.0400.pdf.

这篇关于硬币变化：贪婪的方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！