用特定账单表示金额 [英] Representing an amount of money with specific bills

问题描述

我想在 Racket 中编写一个函数，它需要一笔钱和一个特定账单价值的列表，然后返回一个列表，其中包含每种类型使用的账单数量以构成给定金额.例如 (calc 415 (list 100 10 5 2 1)) 应该返回 '(4 1 1 0 0).

I want to write a function in Racket which takes an amount of money and a list of specific bill-values, and then returns a list with the amount of bills used of every type to make the given amount in total. For example (calc 415 (list 100 10 5 2 1)) should return '(4 1 1 0 0).

我以这种方式尝试过，但这不起作用:/说实话，我想我还没有完全理解您可以/不能使用 Racket 中的 set! 做什么.

I tried it this way but this doesn't work :/ I think I haven't fully understood what you can / can't do with set! in Racket, to be honest.

(define (calc n xs)
  (cond ((null? xs) (list))
        ((not (pair? xs)) 
          (define y n) 
          (begin (set! n (- n (* xs (floor (/ n xs)))))
                 (list (floor (/ y xs))) ))
        (else (append (calc n (car xs))
                      (calc n (cdr xs))))))

推荐答案

这个问题需要一些简单的递归非确定性编程.

This problem calls for some straightforward recursive non-deterministic programming.

• 我们从给定的金额和给定的纸币列表面额开始，显然每张纸币的金额不受限制(否则，这将是一个不同的问题).
• 在每个时间点，我们可以使用最大的账单，也可以不使用.
• 如果我们使用它，总金额会减少账单的价值.
• 如果总数为 0，我们就有了解决方案！
• 如果总数是负数，则无效，所以我们应该放弃这条路.

• We start with a given amount, and a given list of bill denominations, with unlimited amounts of each bill, apparently (otherwise, it'd be a different problem).
• At each point in time, we can either use the biggest bill, or not.
• If we use it, the total sum lessens by the bill's value.
• If the total is 0, we've got our solution!
• If the total is negative, it is invalid, so we should abandon this path.

此处的代码将遵循我的另一个答案，它找出解决方案的总数(对于您的示例， 不止一个).我们也只需要考虑解决方案本身，而上面提到的代码只计算了它们.

The code here will follow another answer of mine, which finds out the total amount of solutions (which are more than one, for your example as well). We will just have to mind the solutions themselves as well, whereas the code mentioned above only counted them.

我们可以将其编码为 recursive-backtracking 过程，从最深 递归级别(相当于嵌套循环结构中最深的嵌套循环)调用一个回调用递归创建，这是递归回溯的本质):

We can code this one as a recursive-backtracking procedure, calling a callback with each successfully found solution from inside the deepest level of recursion (tantamount to the most deeply nested loop in the nested loops structure created with recursion, which is the essence of recursive backtracking):

(define (change sum bills callback)
  (let loop ([sum sum] [sol '()] [bills bills])    ; "sol" for "solution"
    (cond
       ((zero? sum)   (callback sol))              ; process a solution found
       ((< sum 0)      #f)
       ((null? bills)   #f)
       (else
        (apply
          (lambda (b . bs)                         ; the "loop":
              ;; 1.                                ; either use the first
            (loop (- sum b) (cons b sol) bills)    ;   denomination,
              ;; 2.                                ;   or,
            (loop    sum            sol     bs))   ;   after backtracking, don't!
          bills)))))

它将通过例如调用之一

;; construct `the-callback` for `solve` and call 
;;       (solve ...params the-callback)
;; where `the-callback` is an exit continuation

(define (first-solution solve . params)
  (call/cc (lambda (return)
      (apply solve (append params         ; use `return` as
                     (list return))))))   ; the callback

(define (n-solutions n solve . params)    ; n assumed an integer
  (let ([res '()])                        ; n <= 0 gets ALL solutions
    (call/cc (lambda (break)
        (apply solve (append params
                       (list (lambda (sol)
                               (set! res (cons sol res))
                               (set! n (- n 1))
                               (cond ((zero? n) (break)))))))))
    (reverse res)))

测试，

> (first-solution change 406 (list 100 10 5 2))

'(2 2 2 100 100 100 100)

> (n-solutions 7 change 415 (list 100 10 5 2 1))

'((5 10 100 100 100 100)
  (1 2 2 10 100 100 100 100)
  (1 1 1 2 10 100 100 100 100)
  (1 1 1 1 1 10 100 100 100 100)
  (5 5 5 100 100 100 100)
  (1 2 2 5 5 100 100 100 100)
  (1 1 1 2 5 5 100 100 100 100))

---

关于此代码的结构，请参见.如何在 Lisp 中一次一个地生成列表中元素的所有排列? 它创建嵌套循环，解决方案是可在最里面的循环体中访问.

---

Regarding how this code is structured, cf. How to generate all the permutations of elements in a list one at a time in Lisp? It creates nested loops with the solution being accessible in the innermost loop's body.

关于如何以适当的功能方式编写非确定性算法(一次做出所有可能的选择)，请参阅如何在 DrRacket 中进行 powerset? 和 如何在 Scheme 中查找列表的分区.

Regarding how to code up a non-deterministic algorithm (making all possible choices at once) in a proper functional way, see How to do a powerset in DrRacket? and How to find partitions of a list in Scheme.

这篇关于用特定账单表示金额的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！