用特定账单代表一定金额 [英] 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 maintain the solutions themselves as well, whereas the code mentioned above only counted them.
我们可以将此代码编码为递归回溯过程，并为每个成功找到的解决方案调用一个回调:
We can code this one as a recursively backtracking procedure, with a callback to be called with each successfully found solution:
(define (change sum bills callback)
(let loop ((sum sum) (sol '()) (bills bills)) ; "sol" for "solution"
(cond
((zero? sum) (callback sol))
((< sum 0) #f)
((null? bills) #f)
(else (apply
(lambda (b . bs)
(loop (- sum b) (cons b sol) bills) ; either use the first denomination,
(loop sum sol bs)) ; or backtrack, and don't!
bills)))))
通过其中之一调用它
(define (first-solution proc . params)
(call/cc (lambda (return)
(apply proc (append params
(list (lambda (sol)
(return sol))))))))
(define (n-solutions n proc . params) ; n assumed an integer
(let ([res '()]) ; n <= 0 gets ALL solutions
(call/cc (lambda (break)
(apply proc (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.
关于如何以适当的功能方式编写非确定性算法(一次做出所有可能的选择)的代码，请参见如何在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屋！
