标签: coin-change

几个月前,我找到了一段代码,我正在编写面试.

根据我的评论,它试图解决这个问题:

给定一美分的美分价值(例如200 = 2美元,1000 = 10美元),找到构成美元价值的所有硬币组合.只有便士(1¢),镍(5¢),角钱(10¢)和四分之一(25¢).

例如,如果给出100,答案应该是:

4 quarter(s) 0 dime(s) 0 nickel(s) 0 pennies  
3 quarter(s) 1 dime(s) 0 nickel(s) 15 pennies  
etc.

我相信这可以通过迭代和递归方式解决.我的递归解决方案非常错误,我想知道其他人如何解决这个问题.这个问题的难点在于尽可能提高效率.

所以; 我是一个尝试通过SICP工作的业余爱好者(它是免费的!)并且在第一章中有一个示例程序,旨在计算用美国硬币进行更改的可能方法; (change-maker 100)=> 292.它的实现类似于:

(define (change-maker amount)
  (define (coin-value n)
    (cond ((= n 1) 1)
          ((= n 2) 5)
          ((= n 3) 10)
          ((= n 4) 25)
          ((= n 5) 50)))

  (define (iter amount coin-type)
    (cond ((= amount 0) 1)
          ((or (= coin-type 0) (< amount 0)) 0)
          (else (+ (iter amount
                         (- coin-type 1))
                   (iter (- amount (coin-value coin-type))
                         coin-type)))))

  (iter amount 5))

无论如何; 这是一个树递归过程,作者"留下挑战"找到一个迭代过程来解决同样的问题(即固定空间).我没有幸运得到这个或在沮丧后找到答案.我想知道这对我来说是不是一个大脑放屁,或者是作者和我搞砸了.

我是麻省理工学院开放式课程的SICP课程的初学者,使用视频讲座和在线提供的书籍.昨天我遇到了一个例子,它询问我们是否可以编写一个程序来计算改变任何给定金额的方法的数量.

这个问题有一个简单的解决方案作为递归过程:

(define (count-change amount)
  (cc amount 5))
(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

如果你想检查更多,我从这里拿走它.

他们通过添加以下内容计算使用K种硬币改变数量(N)的数量(N):

1. 没有第一类硬币的改变A的方式(X)的数量.

2. 改变(A - D)的方式(Y)的数量,其中D是fisrt硬币的面额,使用所有K种类型的硬币.

问题是,我只是不明白这一点.接着,他们试图解释说:

"要明白为什么这是真的,请注意改变的方法可以分为两组:那些不使用任何第一种硬币的那些,以及那些使用任何第三种硬币的方法.因此,改变方法的总数对于某些金额等于不使用任何第一种硬币进行金额变更的方式的数量,加上假设我们使用第一种硬币进行变更的方式的数量.(最后一句话)与加法N = X + Y相同？)但后一个数字等于使用第一种硬币后剩余数量的变化方式的数量.(使用此硬币后,它们指的是方式是否使用第一种硬币进行更改？) " …

在一coin-change类问题中，我试图将递归函数重构为迭代。给定一组coin_types，该函数递归地coinr找到支付给定金额 的最小硬币数量sum。

# Any coin_type could be used more than once or it may not be used at all

sub coinr ($sum, @coin_types) { # As this is for learning basic programming 
    my $result = $sum;          # No memoization (dynamic programming) is used
    if $sum == @coin_types.any { return 1 }
    else { for @coin_types.grep(* <= $sum) -> $coin_type {
        my $current = 1 + coinr($sum - $coin_type, @coin_types);
        $result = $current …

我正在尝试解决经典的硬币找零（动态）问题。
为了使用动态方法找到所有独特组合的数量以从无限面额的硬币中获得总和，我使用了以下方法：

/* 
     n - number of coins
     arr[] - coin denominations
     x - total sum
     dp[] - array to store number of combinations at index i.
*/
for (int j = 0; j < n; j++)
     for (int i = 1; i <= x; i++)
          if (arr[j] <= i)
              dp[i] = (long) ((dp[i] + dp[i - arr[j]]) % (1e9 + 7));

这给了我所有唯一可能的combinations计数：
例如：

Input:
n=3 x=9
Coins: 2 3 5

Output:
3

到目前为止，一切都很好。但我观察到，只需交换上面代码片段中的循环，我就得到了所有可能的结果permutations。

Input:
n=3 …

我完全陷入困境,不知道如何解决这个问题.假设我有一个阵列

arr = [1, 4, 5, 10]

和一个数字

n = 8

我需要从arr内等于n的最短序列.所以例如在arr等于n之后的序列

c1 = 5,1,1,1
c2 = 4,4
c3= 1,1,1,1,1,1,1,1

所以在上面的例子中,我们的答案是c2,因为它是arr中等于sum的最短序列.

我不确定找到上述解决方案的最简单方法是什么？任何想法或帮助将非常感激.

谢谢!

编辑:

• 修复了数组
• 数组可能只有正值.
• 我不确定子集问题如何解决这个问题,可能是由于我自己的无知.子集算法总是给出等于和的最短序列吗？例如,子集问题会将c2识别为上述场景中的答案吗？

给定目标金额和硬币面额列表,我的代码应该找到达到目标金额所需的最少硬币.

例子:

• C(78, [1, 5, 10, 25, 50]) = 6

  • 我们可以从3x 25+ 3x 制作78 1,所以需要6个硬币

• C(48, [1, 7, 24, 42]) = 2

  • 48 = 2x 24,所以2个硬币就足够了

• C(35, [1, 3, 16, 30, 50]) = 3

  • 我们可以从2x 16+ 1x 制作35 3,所以3个硬币就足够了

我使用for循环创建了代码,但是如何使其递归？

def C(i, coins, cdict = None):
    if cdict == None:
        cdict = {}
    if i <= 0:
        cdict[i] = 0
        return cdict[i]
    elif i in cdict:
        return cdict[i]
    elif i in coins:
        cdict[i] = 1 …

我在理解各种问题的动态编程解决方案时遇到了问题，特别是硬币找零问题：

“给定值N，如果我们要N分钱找零，并且我们有无限数量的S = {S1，S2，..，Sm}硬币的供应，我们可以用几种方法进行找零？硬币没关系。

例如，对于N = 4和S = {1,2,3}，有四个解：{1,1,1,1}，{1,1,2}，{2,2}，{1， 3}。因此输出应为4。对于N = 10且S = {2，5，3，6}，有五个解决方案：{2,2,2,2,2}，{2,2,3,3}， {2,2,6}，{2,3,5}和{5,5}。因此输出应为5。”

此问题还有另一个变体，解决方案是满足该数量的最少硬币数量。

这些问题看起来非常相似，但是解决方案却非常不同。

进行更改的可能方法的数量：最佳子结构为DP（m，n）= DP（m-1，n）+ DP（m，n-Sm），其中DP是所有硬币的解数，直至第m个硬币，金额= n。

最小数量的硬币：为此的最佳子结构为 DP [i] = Min {DP [i-d1]，DP [i-d2]，... DP [i-dn]} + 1，其中i为总量和d1..dn代表每种硬币面额。

为什么第一个需要二维数组，而第二个需要1-D数组呢？为什么更改方式的最优子结构不是“ DP [i] = DP [i-d1] + DP [i-d2] + ... DP [i-dn] ”，其中DP [i]是我可以通过硬币获得数量的方法的数量。这对我来说听起来合乎逻辑，但会产生错误的答案。为什么在这个问题中需要硬币的第二维，而在最小数量问题中却不需要？

问题链接：

http://comproguide.blogspot.com/2013/12/minimum-coin-change-problem.html http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

提前致谢。我访问的每个网站仅说明了该解决方案的工作原理，而不说明其他解决方案为何不起作用。

动态规划变化问题（有限硬币）。我正在尝试创建一个作为INPUT的程序：

int coinValues[]; //e.g [coin1,coin2,coin3]
int coinLimit[]; //e.g [2 coin1 available,1 coin2 available,...]
int amount; //the amount we want change for.

输出：

int DynProg[]; //of size amount+1.

并且输出应该是一个大小为amount+1的数组，其中每个单元格代表我们需要为单元格索引的数量提供更改的最佳硬币数量。

示例：假设我们在索引：5 处有 Array 的单元格，内容为 2。这意味着，为了改变 5（INDEX）的数量，您需要 2（单元格的内容）硬币（最佳解决方案） .

基本上我需要这个视频的第一个数组(C[p]) 的输出。这是完全相同的问题与大差异的有限公司硬币。 链接到视频。

注意：看视频理解，忽略视频的第二个数组，记住我不需要组合，而是DP数组，这样我就可以找到哪些硬币作为找零。

谢谢你。

假设我有三种类型的硬币——一分钱 (0.01)、一分钱 (0.05) 和一角钱 (0.10)，我想找到兑换一定金额的方法的数量。例如更改 27 美分：

change(amount=27, coins=[1,5,10])

解决此问题的一种更常见的方法是递归/动态地：找到在没有特定硬币的情况下进行更改的方法数量，然后减去该硬币数量并找到使用该硬币进行更改的方法。

但是，我想知道是否有办法使用缓存值和 mod 运算符来做到这一点。例如：

1. 10 美分可以通过 4 种方式更改：

   • 10 便士
   • 1 角钱
   • 2 镍
   • 1 镍，5 便士

2. 5 美分可以通过两种方式更改：

   • 1 镍
   • 5 便士

3. 1-4 美分可以通过 1 种方式改变：

   • 1-4 便士

例如，这是错误的，但我的想法是：

def change(amount, coins=[1,5,10]):
    cache = {10: 4, 5: 2, 1: 1}
    for coin in sorted(coins, reverse=True):
        # yes this will give zerodivision
        # and a penny shouldn't be multiplied
        # but this is just to demonstrate the basic idea …