当给定一些美元价值时如何找到硬币的所有组合 [英] How to find all combinations of coins when given some dollar value

问题描述

我发现了一段我几个月前为面试准备而编写的代码.

I found a piece of code that I was writing for interview prep few months ago.

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

According to the comment I had, it was trying to solve this problem:

给定一些以美分为单位的美元价值(例如 200 = 2 美元，1000 = 10 美元)，找出构成美元价值的所有硬币组合.只允许使用便士 (1¢)、五分硬币 (5¢)、一角硬币 (10¢) 和 25 美分 (25¢).

Given some dollar value in cents (e.g. 200 = 2 dollars, 1000 = 10 dollars), find all the combinations of coins that make up the dollar value. There are only pennies (1¢), nickels (5¢), dimes (10¢), and quarters (25¢) allowed.

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

For example, if 100 was given, the answer should be:

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

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

I believe that this can be solved in both iterative and recursive ways. My recursive solution is quite buggy, and I was wondering how other people would solve this problem. The difficult part of this problem was making it as efficient as possible.

推荐答案

我很久以前研究过一次，你可以阅读我的 关于它的小文章.这是 Mathematica 源.

I looked into this once a long time ago, and you can read my little write-up on it. Here’s the Mathematica source.

通过使用生成函数，您可以得到问题的闭式常数时间解.Graham、Knuth 和 Patashnik 的具体数学就是这本书，其中包含对该问题的相当广泛的讨论.本质上，您定义了一个多项式，其中第 n 个系数是为 n 美元进行更改的方式的数量.

By using generating functions, you can get a closed-form constant-time solution to the problem. Graham, Knuth, and Patashnik’s Concrete Mathematics is the book for this, and contains a fairly extensive discussion of the problem. Essentially you define a polynomial where the nth coefficient is the number of ways of making change for n dollars.

文章的第 4-5 页展示了如何使用 Mathematica(或任何其他方便的计算机代数系统)在几秒钟内用三行代码计算出 10^10^6 美元的答案.

Pages 4-5 of the writeup show how you can use Mathematica (or any other convenient computer algebra system) to compute the answer for 10^10^6 dollars in a couple seconds in three lines of code.

(这是很久以前的事了，在 75Mhz Pentium 上只有几秒钟......)

(And this was long enough ago that that’s a couple of seconds on a 75Mhz Pentium...)

这篇关于当给定一些美元价值时如何找到硬币的所有组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！