我怎样可以在Scheme中利用动态规划来解决零钱兑换问题？

Question

我正在尝试学习Lisp语言，并选择了Guile来解决这个问题：

给定一个整数数组coins，代表不同面额的硬币，以及一个整数amount，代表总金额。

返回组成该金额所需的最少硬币数量。如果无法用任何组合的硬币凑出该金额，则返回-1。

假设你拥有每种硬币的无限数量。

从根本上讲，我理解动态规划的基本原理，可以使用递归和记忆化来节省在较低深度处进行计算的时间，但作为Lisp，我希望它能完美解决这类问题。我遇到的问题是如何返回每个硬币组合的单独列表。

以目标金额为6，硬币为[2, 3]的示例情况来说明，简单的树形结构如下：

正确答案应该是(3 3)，另一个“完整”的解决方案是(2 2 2)。

但是，如果我尝试构建这些东西，我想要使用的形式（不带记忆化）会看起来像这样。

(define get-coins (lambda (coins target) 
    (cond
        ((= target 0) '())
        ; not quite sure how to "terminate" a list here 
        ; An idea is to return (list -1) and then filter 
        ; lists that contain -1
        ((< target 0) ?????) 
        (else
            ; for each coin, recurse
            (map (lambda (v)
                (cons v (get-coins coins (- target v))))))
    )
))

然而，它不会在遍历过程中返回更多的列表。相反，它会创建嵌套的列表。这就是我的问题所在。任何帮助都将不胜感激。

- Kyle Baldwin

---

你的树形算法有误。对于目标值5，它会产生2,3和3,2两个有效且不同的解。 - Will Ness

通常的解决方法是禁止在树的右侧分支以外的任何地方使用最大的硬币。 - Will Ness

Answer 1

我想避免嵌套列表，所以我使用了一个变量results：

(define (get-coins coins target)
  (let ((results '()))

然后我定义了函数get-coins-helper，类似于你的get-coins。每当我找到一些可能的结果时，我使用set!来更新results：

 (letrec ((get-coins-helper
              (lambda (coins target result)
                (cond ((= target 0) (set! results (cons result results)))
                      ((< target 0) '())
                      (else (map (lambda (value)
                                   (get-coins-helper coins
                                                     (- target value)
                                                     (cons value result)))
                                 coins))))))

然后我调用了(get-coins-helper coins target '())来查找所有可能的结果，最后，我检查了results的值，并返回-1（如果results为空）或results中最短的元素：

      (if (null? results)
          -1
          (car (sort results (lambda (x y) (< (length x)
                                              (length y))))))

完整代码：

(define (get-coins coins target)
  (let ((results '()))
    (letrec ((get-coins-helper
              (lambda (coins target result)
                (cond ((= target 0) (set! results (cons result results)))
                      ((< target 0) '())
                      (else (map (lambda (value)
                                   (get-coins-helper coins
                                                     (- target value)
                                                     (cons value result)))
                                 coins))))))
      (get-coins-helper coins target '())
      (if (null? results)
          -1
          (car (sort results (lambda (x y) (< (length x)
                                              (length y)))))))))

一些测试：

> (get-coins '(2 3) 6)
'(3 3)
> (get-coins '(2 3) 1)
-1

- Martin Půda

---

我发现一个使用Racket的用户！（Guile没有empty?）。 - Shawn

（或者除非您导入SRFI-1） - Shawn

谢谢 - 这只是一个提醒，对于未来的人们自愿承受这种折磨。empty?（Racket）在检查空列表时与null?（Guile）执行相同的操作。那就是@Shawn所指的代码。 - Kyle Baldwin

只是一点小建议，当然你遵循了原帖的代码结构，但它可能会做大量冗余工作，为每个解决方案生成所有排列组合，而有序的硬币集合就足够了。例如，尝试目标值为5。 - Will Ness

Answer 2

使用折叠函数fold来选择最佳方案。结果是一个列表，其中car是硬币的数量，cdr是所选硬币的列表。如果没有可行的解决方案，则返回(+inf.0)。

(use-modules (srfi srfi-1))

(define (get-coins coins target)
  (fold (lambda (coin best)
          (let [(target (- target coin))]
            
            (cond [(zero? target)
                   (list 1 coin)]
                  
                  [(positive? target)
                   (let* [(res (get-coins coins target))
                          (score' (1+ (car res)))]
                     (if (< score' (car best))
                         (cons score' (cons coin (cdr res)))
                         best))]
                  
                  [(negative? target)
                   best])))
        (list +inf.0)
        coins))

(get-coins (list 2) 6)
$8 = (3 2 2 2)

(get-coins (list 2 3) 6)
$9 = (2 3 3)

(get-coins (list 9) 6)
$10 = (+inf.0)

- Stefano Barbi

Answer 3

如果你仔细阅读问题，你只需要跟踪到达目标金额所需的硬币数量。你不需要生成每一个可能的硬币组合来达到目标，只需要最小化硬币数量的那个组合。而且你甚至不需要记住那个特定组合是什么，只需要知道它的长度。这使事情变得简单了一些，因为不需要构建任何列表。

对于每种可能用于达到目标的硬币面额（因此没有比目标和当前总和之间差异更大的硬币），获取使用其中一种硬币和不使用硬币的计数，并返回最小值（如果没有选项，则返回-1）。

(define (get-coins coins target)
  (calculate-coins coins 0 0 target))

;; Do all the work in a helper function
(define (calculate-coins coins coin-count amount target)
  (cond
   ((= amount target) coin-count) ; Success
   ((null? coins) -1) ; Failure
   ((> (car coins) (- target amount)) ; Current coin denomination is too big; skip it
    (calculate-coins (cdr coins) coin-count amount target))
   (else
    ;; Cases to consider:
    ;;  Adding one of the current coin to the total and leaving open using more
    ;;  Not using any of the current coins
    (let ((with-first
           (calculate-coins coins (+ coin-count 1) (+ amount (car coins)) target))
           (without-first
            (calculate-coins (cdr coins) coin-count amount target)))
      (cond
       ((= with-first -1) without-first)
       ((= without-first -1) with-first)
       (else (min with-first without-first)))))))

如果您确实想要获取每个硬币的所有可能组合，一种方法是对于使用给定硬币的每个组合列表，使用append将其与先前方式的列表组合：

(use-modules (srfi srfi-1))
(define (get-coins2 coins target)
  (define (helper target) ; This time define a nested helper function
    (fold
     (lambda (coin ways)
       (cond
        ((= coin target) (cons (list coin) ways))
        ((< coin target)
         (append
          (map (lambda (c) (cons coin c))
               (helper (- target coin)))
          ways))
        (else ways)))
     '()
     coins))
  (let* ((ways (helper target))
         (table (make-hash-table (length ways))))
    ;; Store each combination as a key in a hash table to remove duplicates
    (for-each (lambda (way) (hash-set! table (sort-list way <) #t)) ways)
    (hash-map->list (lambda (k v) k) table)))

示例：

scheme@(guile-user)> (load "coins.scm")
scheme@(guile-user)> (get-coins '(2) 6)
$1 = 3
scheme@(guile-user)> (get-coins2 '(2) 6)
$2 = ((2 2 2))
scheme@(guile-user)> (get-coins '(2 3) 6)
$3 = 2
scheme@(guile-user)> (get-coins2 '(2 3) 6)
$4 = ((2 2 2) (3 3))
scheme@(guile-user)> (get-coins '(9) 6)
$5 = -1
scheme@(guile-user)> (get-coins2 '(9) 6)
$6 = ()
scheme@(guile-user)> (get-coins2 '(2 3) 12)
$7 = ((3 3 3 3) (2 2 2 3 3) (2 2 2 2 2 2))
scheme@(guile-user)> (get-coins '(5 2 3 4) 21)
$8 = 5
scheme@(guile-user)> (get-coins2 '(5 2 3 4) 21)
$9 = ((2 2 2 5 5 5) (2 3 3 4 4 5) (2 4 5 5 5) (3 3 3 4 4 4) (2 2 3 4 5 5) (4 4 4 4 5) (2 2 4 4 4 5) (2 2 3 3 3 4 4) (2 2 2 2 2 3 4 4) (2 2 2 2 4 4 5) (3 3 3 3 4 5) (2 2 2 2 3 3 3 4) (2 2 2 2 2 2 2 3 4) (2 2 2 2 2 2 4 5) (3 3 3 3 3 3 3) (2 2 3 3 3 3 5) (2 2 2 2 2 2 3 3 3) (2 2 2 2 2 3 3 5) (3 3 5 5 5) (2 2 2 2 2 2 2 2 2 3) (2 2 2 2 3 5 5) (2 2 2 2 2 2 2 2 5) (2 3 4 4 4 4) (2 2 2 3 4 4 4) (2 3 3 3 3 3 4) (2 2 2 3 3 4 5) (2 2 2 3 3 3 3 3) (2 3 3 3 5 5) (3 4 4 5 5))
scheme@(guile-user)> (filter (lambda (way) (= (length way) 5)) (get-coins2 '(5 2 3 4) 21))
$10 = ((2 4 5 5 5) (4 4 4 4 5) (3 3 5 5 5) (3 4 4 5 5))

- Shawn

---

你的函数在 (get-coins '(5 2 3 4) 21) 上失败了，期望结果为 5 '(5 5 5 2 4)。 - Stefano Barbi

@StefanoBarbi 发现得好；已修复。（尽管还有其他5个硬币的可能性） - Shawn

Answer 4

有很多方法可以做到这一点，这里是一种蛮力解决方案。它不够优雅，但很简单。

(define mk/pairs
  (lambda (sum coin/list)
    ((lambda (s) (s s
               (map (lambda (x) (iota (+ 1 (quotient sum x)))) coin/list)
               (lambda (s) s) ))
     (lambda (s l* ret)
       (if (null? l*)
           (ret '(()))
           (s s (cdr l*)
              (lambda (r)
                (ret (apply
                      append
                      (map (lambda (x) (map (lambda (y) (cons y x)) (car l*)))
                       r))))))))))

(define cost
  (lambda (s pair coin/list)
    (let ((sum (apply + (map * pair coin/list))))
      (and (= s sum) pair))))

(define solve
  (lambda (sum coin/list)
    (let ((pairs (mk/pairs sum coin/list)))
      (let ((solutions
             (sort (filter (lambda (x) x)
                           (map (lambda (p) (cost sum p coin/list)) pairs))
                   (lambda (p1 p2)
                     (< (apply + p1)
                        (apply + p2))))))
        (if (null? solutions)
            "fail"
            (car solutions))))))

一个测试看起来像这样：

% mit-scheme < coins.scm
MIT/GNU Scheme running under GNU/Linux

1 ]=> (solve 8 '(2 3 1))
;Value: (1 2 0)

1 ]=> (solve 6 '(2 3))
;Value: (0 2)

这意味着在第一个例子中，您有1个面值为2的硬币和2个面值为3的硬币，在第二个例子中有2个面值为3的硬币。

我使用了标准的R6RS，因此您应该能够直接从mit/scheme转换到guile。

- alinsoar