硬币找零算法

Question

硬币找零算法

algorithm

10

假设我有一组硬币，其面值为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.

注意：这不是作业，只是对此问题的修改。

- Rohit Banga

10

帮助某个人解决一个家庭作业问题并不能立刻让他们成为A+学生。在某些情况下，它可能会帮助这个学生“茅塞顿开”，成长为一位聪明的年轻开发者。然而，那些反复这种行为的人（不尝试自己解决问题）更有可能只是因为他们没有挑战自己而从未成长。他们最终很可能会遭受惨败，尤其是考试日。至少在我所在的学校，考试占据了我们成绩的很大一部分，家庭作业实际上并不重要（在某门课程中，考试占100%）。 - jason

4个回答

0

C#代码的解决方案

    public static long findPermutations(int n, List<long>  c)
{

    // The 2-dimension buffer will contain answers to this question:
    // "how much permutations is there for an amount of `i` cents, and `j`
    // remaining coins?" eg. `buffer[10][2]` will tell us how many permutations
    // there are when giving back 10 cents using only the first two coin types
    // [ 1, 2 ].
    long[][] buffer = new long[n + 1][];
    for (var i = 0; i <= n; ++i)
        buffer[i] = new long[c.Count + 1];

    // For all the cases where we need to give back 0 cents, there's exactly
    // 1 permutation: the empty set. Note that buffer[0][0] won't ever be
    // needed.
    for (var j = 1; j <= c.Count; ++j)
        buffer[0][j] = 1;

    // We process each case: 1 cent, 2 cent, etc. up to `n` cents, included.
    for (int i = 1; i <= n; ++i)
    {

        // No more coins? No permutation is possible to attain `i` cents.
        buffer[i][0] = 0;

        // Now we consider the cases when we have J coin types available.
        for (int j = 1; j <= c.Count; ++j)
        {

            // First, we take into account all the known permutations possible
            // _without_ using the J-th coin (actually computed at the previous
            // loop step).
            var value = buffer[i][j - 1];

            // Then, we add all the permutations possible by consuming the J-th
            // coin itself, if we can.
            if (c[j - 1] <= i)
                value += buffer[i - c[j - 1]][j];

            // We now know the answer for this specific case.
            buffer[i][j] = value;
        }
    }

    // Return the bottom-right answer, the one we were looking for in the
    // first place.
    return buffer[n][c.Count];
}

- Ahmed Zamil

0

这是一个Python中动态规划算法的示例实现。它比Jason描述的算法简单，因为它只计算他描述的2D表格中的1行。

请注意，使用此代码作弊会让僵尸Dijkstra哭泣。

import sys
def get_best_coins(coins, target):
    costs = [0]
    coins_used = [None]
    for i in range(1,target + 1):
        if i % 1000 == 0:
            print '...', 
        bestCost = sys.maxint
        bestCoin = -1
        for coin in coins:
            if coin <= i:
                cost = 1 + costs[i - coin]
                if cost < bestCost:
                    bestCost = cost
                    bestCoin = coin
        costs.append(bestCost)
        coins_used.append(bestCoin)
    ret = []    
    while target > 0:
        ret.append(coins_used[target])
        target -= coins_used[target]
    return ret

coins = [1,10,25]
target = 100033
print get_best_coins(coins, target)

- RossFabricant

-1

以下是动态规划的自底向上方法。

        int[] dp = new int[amount+ 1]; 
        Array.Fill(dp,amount+1);
        dp[0] = 0;
        for(int i=1;i<=amount;i++)
        {
            for(int j=0;j<coins.Length;j++)
            {
                if(coins[j]<=i) //if the amount is greater than or equal to the current coin
                {
                    //refer the already calculated subproblem dp[i-coins[j]]
                    dp[i] = Math.Min(dp[i],dp[i-coins[j]]+1);
                }
            }
        }
        if(dp[amount]>amount)
            return -1;
        return dp[amount];
    }

- jo_Veera

谢谢你的好回答。你想一起发布它的复杂度吗？ - akshay

1

时间复杂度：O(S*n)，空间复杂度：O(n) 其中n表示数量，S表示硬币的数量。 - jo_Veera

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jason · Accepted Answer

这是一个经典的动态规划问题（请注意，贪心算法并不总是适用于此问题！）。假设硬币按照 a_1 > a_2 > ... > a_k = 1 的顺序排列。我们定义一个新的问题，即找到使用硬币 a_i > a_(i + 1) > ... > a_k 找零 j 的最小硬币数量。我们希望解决的问题是任意 j（满足 1 <= j <= n）的 (1, j) 问题。假设 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。