确定找零的组合对于给定的量 [英] Determine the combinations of making change for a given amount

问题描述

我的任务是编写使用蛮力，以确定不同的方式，转变为一定量的相关组合数的算法。便士（1分钱），镍（5美分），硬币（10美分），而四分之一（25美分）的变化将用下面的硬币生产。

My assignment is to write an algorithm using brute force to determine the number of distinct ways, an related combinations of change for given amount. The change will be produced using the following coins: penny (1 cent), nickel (5 cents), dime (10 cents), and quarter (25 cents).

例如。

输入：16（这意味着16美分的变化）

Input: 16 (it means a change of 16 cents)

输出：可以产生6种不同的方式，它们分别是：

Output: can be produced in 6 different ways and they are:

1. 16便士。
2. 11便士，1镍
3. 在6便士，1毛钱
4. 在6便士，2镍
5. 1分钱，3镍
6. 1分钱，1镍，1毛钱

我的算法必须生产出所有可能的变化组合进行规定的变化量。

My algorithm must produce all possible change combinations for a specified amount of change.

我在一个完全丧失对如何甚至开始启动这样一个算法。任何输入或洞察力，让我去将是真棒。

I am at a complete loss as to how to even begin starting an algorithm like this. Any input or insight to get me going would be awesome.

推荐答案

确定。让我来解释一个想法，一个蛮力算法。我将在这里使用递归。

Ok. Let me explain one idea for a brute force algorithm. I will use recursion here.

让你需要的 C 美分的改变的。然后考虑 C 为

Let's you need a change of c cents. Then consider c as

c = p * PENNY + n * NICKEL + d * DIME + q * QUARTER

或简称

c = ( p * 1 ) + ( n * 5 ) + ( d * 10 ) + ( q * 25 )

现在你需要去通过所有可能的值 P ， N ， ð和①这等于 C值。使用递归，对于每一个 p在[0，maximumPennies] 通过每个 N的[0，maximumNickels] 。对于每个 N 通过每个 D在[0，maximumDimes] 。对于每个 D 通过每个●在[0，maximumQuarters] 。

Now you need to go through all the possible values for p, n, d and q that equals the value of c. Using recursion, for each p in [0, maximumPennies] go through each n in [0, maximumNickels]. For each n go through each d in [0, maximumDimes]. For each d go through each q in [0, maximumQuarters].

p in [0, maximumPennies] AND c >= p
  |
  +- n in [0, maximumNickels] AND c >= p + 5n
       |
       +- d in [0, maximumDimes] AND c >= p + 5n + 10d
            |
            +- q in [0, maximumQuarters] AND c >= p + 5n + 10d + 25q

有关在这些步骤中的任何平等的，你得到了一个解决方案。

For any equality in these steps you got a solution.

这篇关于确定找零的组合对于给定的量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！