algorithm - 换币算法

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.

注意:不是作业只是对this的修改问题

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 .