查找次数最少需要硬币，可以使任何改变，从1到99美分 [英] Find the least number of coins required that can make any change from 1 to 99 cents

问题描述

最近我挑战我的同事写一个算法来解决这个问题：

Recently I challenged my co-worker to write an algorithm to solve this problem:

查找次数最少需要硬币，可以使任何改变，从1到99美分。硬币只能是便士（1），镍（5），助攻（10），和宿舍（25），并且必须能够使每一个值从1到99（以1分为单位）使用这些硬币。

Find the least number of coins required that can make any change from 1 to 99 cents. The coins can only be pennies (1), nickels (5), dimes (10), and quarters (25), and you must be able to make every value from 1 to 99 (in 1-cent increments) using those coins.

不过，我意识到，我真的不知道如何做到这一点我自己没有审查硬币的每一个可能的组合。必须有解决这个问题的一个更好的办法，但我不知道这种类型的算法的通用名称将被称为，我不能想出一个办法来简化其超越看着每一个解决方案。

However, I realized that I don't actually know how to do this myself without examining every possible combination of coins. There has to be a better way of solving this problem, but I don't know what the generic name for this type of algorithm would be called, and I can't figure out a way to simplify it beyond looking at every solution.

我想知道是否有人可以点我在正确的方向，或提供了一个算法的效率更高。

I was wondering if anybody could point me in the right direction, or offer up an algorithm that's more efficient.

推荐答案

你要找的是什么的动态规划的。

您实际上并不需要列举所有可能的组合，每一个可能的值，因为你可以在previous答案上建立的。

You don't actually have to enumerate all the possible combinations for every possible values, because you can build it on top of previous answers.

您的算法需要考虑2个参数：

You algorithm need to take 2 parameters:

• 在可能的硬币值的列表，在这里 [1，5，10，25]
• 的范围覆盖，这里 [1，99]

• The list of possible coin values, here [1, 5, 10, 25]
• The range to cover, here [1, 99]

和的目标是计算的设定所需的该范围内的硬币的最小

And the goal is to compute the minimal set of coins required for this range.

最简单的方法是进行在一个底向上的方式：

The simplest way is to proceed in a bottom-up fashion:

Range     Number of coins (in the minimal set)
          1   5   10   25
[1,1]     1
[1,2]     2
[1,3]     3
[1,4]     4
[1,5]     5
[1,5]*    4   1             * two solutions here
[1,6]     4   1
[1,9]     4   1
[1,10]    5   1             * experience tells us it's not the most viable one :p
[1,10]    4   2             * not so viable either
[1,10]    4   1   1
[1,11]    4   1   1
[1,19]    4   1   1
[1,20]    5   1   1         * not viable (in the long run)
[1,20]    4   2   1         * not viable (in the long run)
[1,20]    4   1   2

这是有点容易，在每一步，我们可以通过最多一个硬币将继续进行，我们只需要知道在哪里。这归结于该范围 [X，Y] 包含在事实上 [X，Y + 1] 因此，对于的最小集[X，Y + 1] 应包括的最小集[X，Y] 。

It is somewhat easy, at each step we can proceed by adding at most one coin, we just need to know where. This boils down to the fact that the range [x,y] is included in [x,y+1] thus the minimal set for [x,y+1] should include the minimal set for [x,y].

正如你可能已经注意到了，虽然，有时也有优柔寡断，即多套有硬币数相同。在这种情况下，只能在后来决定哪一个应被丢弃。

As you may have noticed though, sometimes there are indecisions, ie multiple sets have the same number of coins. In this case, it can only be decided later on which one should be discarded.

这应该可以提高其运行时间，注意，添加一个硬币通常，您可以覆盖更大的范围内，你把它添加了一个，我认为当。

It should be possible to improve its running time, when noticing that adding a coin usually allows you to cover a far greater range that the one you added it for, I think.

例如，请注意：

 [1,5]    4*1  1*5
 [1,9]    4*1  1*5

我们添加镍覆盖 [1,5] 但是这给我们到 [1,9] 免费的！

we add a nickel to cover [1,5] but this gives us up to [1,9] for free!

然而，当那些令人发指的输入集处理 [2,3,5,10,25] 来覆盖 [2,99] ，我不能确定如何快速检查的范围涵盖了一套新的，否则会被实际更有效。

However, when dealing with outrageous input sets [2,3,5,10,25] to cover [2,99], I am unsure as how to check quickly the range covered by the new set, or it would be actually more efficient.

这篇关于查找次数最少需要硬币，可以使任何改变，从1到99美分的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！