硬币数量有限的硬币兑换算法 - 方案

Question

我需要编写程序 change 来获取一笔钱和可用硬币的列表，以及 returns 多种可能的方式 用这些硬币支付钱。正如我所说，硬币是有限的。

示例：

(change 10 '(5 5 10)) → 2
;; [1 coin of 10 ,2 coins of 5]

(change 5 '(1 1 1 2 2 5 10)) → 3
;; [1 coin of 5, 1 coin of 2 and 3 coins of 1, 2 coins of 2 and 1 coin of 1]

我试过这个：

(define (change sum coins)
  (if (< sum 0)
      0
      (if (= sum 0)
          1
          (if (and (> sum 0) (<= (length coins) 0))
            0
            (+ (change (- sum (car coins)) (cdr coins)) 
               (change sum (cdr coins)))))))

但我无法摆脱一些重复计数... 第二个示例的输出不是 3，而是：

(change 5 '(1 1 1 2 2 5 10)) → 6

如何解决这个问题？

（Racket 中的代码应该是运行，纯函数式，不使用任何内置方法。我更喜欢递归。唯一允许的数据结构是 List 和 Pair）

Answer 1

:

ways( 0  , _ ) = 1
ways( sum, _ ) | sum < 0 = 0
ways( sum, 0 ) | sum > 0 = 0
ways( sum, k ) = ways( sum, k - 1 )
                 +
                 ways( sum - first_denomination(k),  k )

也就是

               = ways( sum, k - 1 )
                 +
                 ways( sum - first_denomination(k),  k - 1 )
                 +
                 ways( sum - 2*first_denomination(k),  k )
               = ......
                 ......
               = ways( sum, k - 1 )
                 +
                 ways( sum - first_denomination(k),  k - 1 )
                 +
                 ways( sum - 2*first_denomination(k),  k - 1 )
                 +
                 ways( sum - 3*first_denomination(k),  k - 1 )
                 +
                 ......

（直到基本情况）。因此，有限的硬币找零是

ways( sum, [ [c, n], ...t] ) = 
                 ways( sum, t )           ; taking none of c
                 +
                 ways( sum - c,  t )      ; taking one of c
                 +
                 ways( sum - 2*c,  t )    ; taking two of c
                 +
                 ...
                 +
                 ways( sum - n*c,  t )    ; taking n c-valued coins

使用适当调整的基本案例。

剩下的就是用 Scheme 语法写下这个东西，这样你就可以称它为

(change 5 '((1 3) (2 2) (5 1) (10 1)) ) → 3

Answer 2

完成！我的算法很简单，使用这个 remove-all 方法：

(define remove-all
  (lambda (x lst)
    (if (empty? lst)
        '()
    (if (= (car lst) x)
        (remove-all x (cdr lst))
    (cons (car lst) 
          (remove-all x (cdr lst)))))))

(define payment
    (lambda (n coins-lst)
        (if (< n 0)
            0
        (if (= n 0)
            1
        (if (and (> n 0) (empty? coins-lst))
            0
        (+ (payment  (- n (car coins-lst))  (cdr coins-lst)) 
           (payment n (remove-all (car coins-lst) coins-lst))))))))

谢谢你的建议！

硬币数量有限的硬币兑换算法 - 方案

Coin Change Algorithm with limited coins - Scheme

algorithm

scheme

coin-change

racket