为给定的大金额找到最小硬币数量的算法

Question

我只是想知道对于找到总和为数字 S 的最小硬币数量的经典问题是否有任何有效和最佳的算法，其中 S 可以非常大（高达 10^16）。在这种情况下，硬币是 (2, 5, 10)。在这种情况下，DP 解决方案效率不够高，所以我想知道贪婪的方法是否适用于这组特定的硬币，但我不确定。

谢谢！

Answer 1

为了尽量减少硬币数量，我们通常注意到要达到 20，我们需要两个 10-coins。（没有 2-coins 也没有 5-coins）。

更一般地说，要接近 10k（k 是 10 的倍数），我们只需要 10 个硬币。

现在对于不是 10 的倍数的总和，我们可能希望使用最多 10 个硬币。说 S = 10k + 2。硬币的最小值是k+1。 (k 10-coins, and one 2-coin).

所以目标是找到 (k,r)，这样 S = 10k +r, (r < 10).

我们通常通过使用 % 运算符来做到这一点。

r = S % 10
k = S - S % 10

现在为每个 r

找到 2-coins 和 5-coins 所需的所有组合

2=2
4=2+2
5=5
6=2+2+2
7=5+2
8=2+2+2+2
9=5+2+2
1=5+2+2+2 (%10)
3=5+2+2+2+2 (%10)

我把案例1和案例3放在最下面，因为它们是特例

要达到 21，我们需要达到 10，然后 11 (5+2+2+2)

同样适用于 23 我们不能去 20，我们需要去 10，然后制作 13（用 5+2+2+2 ).

关键是用 a 2-coins 和 b 5-coins 的组合求和，这样 2a + 5b = r % 10

终于

对于 S%10=r 不在 {1, 3} 中，使用 k 10-coins 到达 (S - (S%10))=10k 并完成
否则 (S - 10 - S%10)=10(k-1) 与 k-1 10-coins 并完成

如@Iłya Bursov 所指出的最后说明，我们不能为 S=1 或 S=3 做到这一点。

其他人S都能到达

Answer 2

这是在 Python 中概括@grodzi 的解决方案。解决方案取决于没有公因数的硬币面额；如果他们这样做，您可以通过将所有内容除以 highest common factor 来调整解决方案，并拒绝该除法有余数的输入。

对于足够大的输入，每个求和都是可能的。在这种情况下，"Sufficiently large" 表示在可能的 c 总和中的第一个运行之后，其中 c 是最大的硬币面值。我们可以做动态规划来计算解决方案，直到找到长度为 c 的运行，然后每个金额都可以通过取适当数量的面额硬币来解决 c 远，减少总和到这个范围内。

初始化阶段的时间复杂度最多为O(f(coins) * len(coins)) 其中函数f 给出硬币面额集合的 Frobenius number。 make_change 方法的时间复杂度是 O(len(coins)) 加上进行整数除法和余数运算的复杂度，在一个有界整数的语言。

from collections import Counter

class ChangeMaker:
    def __init__(self, *denominations):
        denominations = sorted(denominations, reverse=True)
        self.c = denominations[0]
        self.cache = [Counter()]

        def solve(n):
            for d in denominations:
                if d <= n and self.cache[n - d] is not None:
                    return Counter({ d: 1 }) + self.cache[n - d]
            return None

        run_length = 0
        while run_length < self.c:
            r = solve(len(self.cache))
            self.cache.append(r)
            if r is not None:
                run_length += 1
            else:
                run_length = 0

    def make_change(self, n):
        if n < len(self.cache):
            return self.cache[n]
        else:
            diff = n - len(self.cache) + self.c
            div = diff // self.c
            rem = diff % self.c
            cached = self.cache[len(self.cache) - self.c + rem]
            return Counter({ self.c: div }) + cached

示例：

>>> c = ChangeMaker(2, 5, 10)
>>> c.cache
[Counter(),
 None,
 Counter({2: 1}),
 None,
 Counter({2: 2}),
 Counter({5: 1}),
 Counter({2: 3}),
 Counter({5: 1, 2: 1}),
 Counter({2: 4}),
 Counter({2: 2, 5: 1}),
 Counter({10: 1}),
 Counter({2: 3, 5: 1}),
 Counter({10: 1, 2: 1}),
 Counter({2: 4, 5: 1})]
>>> c.make_change(123456789011)
Counter({10: 12345678900, 2: 3, 5: 1})
>>> c.make_change(123456789013)
Counter({10: 12345678900, 2: 4, 5: 1})

为给定的大金额找到最小硬币数量的算法

algorithm for finding minimum number of coins for a given large sum

algorithm

coin-change