硬币改变算法

Question

假设我有一组面额为a1,a2,... ak的硬币.

已知其中一个等于1.

我想使用最小数量的硬币对所有整数1到n进行更改.

任何关于算法的想法.

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.

注意:不是作业只是修改这个问题

Answer 1

这是一个经典的动态编程问题(首先请注意,贪婪算法并不总是在这里工作!).

假设硬币是按顺序排列的a_1 > a_2 > ... > a_k = 1.我们定义了一个新问题.我们说(i, j)问题是要找到j使用硬币进行更改的最小硬币数量a_i > a_(i + 1) > ... > a_k.我们要解决的问题是(1, j)任何j有1 <= j <= n.说这C(i, j)就是(i, j)问题的答案.

现在,考虑一个实例(i, j).我们必须决定我们是否使用其中a_i一枚硬币.如果我们不是,我们只是解决(i + 1, j)问题,答案是C(i + 1, j).如果我们是,我们通过改变来完成解决方案j - a_i.要使用尽可能少的硬币来做到这一点,我们想要解决(i, j - a_i)问题.我们安排事情,以便我们已经解决了这两个问题,然后:

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

现在弄清楚最初的案例是什么以及如何将其翻译成您选择的语言,你应该好好去.

如果您想尝试另一个需要动态编程的有趣问题,请查看Project Euler Problem 67.