给定一些美元价值时如何找到硬币的所有组合 [英] 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¢）。

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奔腾上还需要几秒钟的时间...）

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

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