投币改变算法 [英] Coin changing algorithm

问题描述

假设我有一组具有A1面额硬币，A2，... AK。

Suppose I have a set of coins having denominations a1, a2, ... ak.

其中之一已知是等于1

One of them is known to be equal to 1.

我要做出改变所有使用硬币的最低数量的整数1到n。

I want to make change for all integers 1 to n using the minimum number of coins.

任何想法的算法。

eg. 1, 3, 4 coin denominations
n = 11
optimal selection is 3, 0, 2 in the order of coin denominations.

n = 12
optimal selection is 2, 2, 1.

注：不做作业只是修改这个的问题

推荐答案

这是（首先注意的贪心算法并不总能在这里工作！）。一个典型的动态规划问题

This is a classic dynamic programming problem (note first that the greedy algorithm does not always work here!).

假设硬币是有序的，这样 A_1＆GT; A_2＆GT; ...＆GT; a_k = 1 。我们定义一个新的问题。我们说（I，J）问题是要找到硬币找零的Ĵ使用硬币的最低数量 A_I＆GT; A_第（i + 1）＆GT; ...＆GT; a_k 。我们要解决的问题是（1，J）任何Ĵ与 1＆LT = J＆LT; = N 。再说说 C（I，J）的答案（I，J）的问题。

Assume the coins are ordered so that a_1 > a_2 > ... > a_k = 1. We define a new problem. We say that the (i, j) problem is to find the minimum number of coins making change for j using coins a_i > a_(i + 1) > ... > a_k. The problem we wish to solve is (1, j) for any j with 1 <= j <= n. Say that C(i, j) is the answer to the (i, j) problem.

现在，考虑一个实例（I，J）。我们必须决定我们是否正在使用的 A_I 硬币之一。如果我们没有，我们只是解决一个（我+ 1，J）的问题，答案是 C（I + 1，J）。 A_I - 如果我们有，我们通过变化Ĵ完成的解决方案。要使用尽可能少的硬币，有可能做到这一点，我们要解决的（I，J - A_I）的问题。我们安排的事情让这两个问题都已经解决了我们，然后：

Now, consider an instance (i, j). We have to decide whether or not we are using one of the a_i coins. If we are not, we are just solving a (i + 1, j) problem and the answer is C(i + 1, j). If we are, we complete the solution by making change for j - a_i. To do this using as few coins as possible, we want to solve the (i, j - a_i) problem. We arrange things so that these two problems are already solved for us and then:

C(i, j) = C(i + 1, j)                         if a_i > j
        = min(C(i + 1, j), 1 + C(i, j - a_i)) if a_i <= j

现在找出最初的案件，如何转换到您所选择的语言，你应该是好去。

Now figure out what the initial cases are and how to translate this to the language of your choice and you should be good to go.

如果你想试试你的手在另一个有趣的问题，需要动态规划，看项目欧拉的问题67 。

If you want to try you hands at another interesting problem that requires dynamic programming, look at Project Euler Problem 67.

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