最优化的硬币适合的钱给定的总和 [英] Most optimal coin fit for a given sum of money

问题描述

在可能的最优化的方式你如何达到一个给定的款项给定一组硬币？

How would you reach a given sum in the most optimal manner possible given a set of coins ?

让我们说，在这种情况下，我们随机数的1，5，10，20和50美分硬币的最大硬币得到优先考虑。

Let's say that in this case we have random numbers of 1, 5, 10, 20 and 50 cent coins with the biggest coins getting the priority.

我的第一直觉是使用所有的最大的硬币可能适合再使用了下最小的硬币值，如果总和超过了。

My first intuition would be to use all the biggest coins possible to fit and then use up the next smallest coin in value if the sum is exceeded.

这会做的还是有什么不足之处，以这种方式？有没有更有效的办法是什么？

Would this do or are there any shortfalls to this approach ? Are there any more efficient approaches ?

推荐答案

有不足之处简单地给予了最大的硬币第一。

There are shortfalls to simply giving out the largest coins first.

假设你的自动售货机，每一枚硬币的除了20每50℃，20℃和1c硬币，你必须在变革提供60℃。

Let's say your vending machine is out of every coin except twenty each of 50c, 20c and 1c coins and you have to deliver 60c in change.

一个优先考虑大（或贪婪）方案会给你一千金币一50C硬币十1C硬币。

A "prioritise-largest" (or greedy) scheme will give you eleven coins, one 50c coin and ten 1c coins.

更好的解决方案为三20c的硬币。

The better solution is three 20c coins.

贪婪的方案只给你的本地的最佳解决方案。对于全局最优解，你通常需要检查所有的可能性（虽然可能有极小型算法，以减少搜索空间），以肯定其为交付的变化，通常是相当之内可计算的限制。

Greedy schemes only give you local optimum solutions. For global optima, you generally need to examine all possibilities (though there may be minimax-type algorithms to reduce the search space) to be certain which, for delivering change, is usually quite within the limits of computability.

这篇关于最优化的硬币适合的钱给定的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！