算法笔试题：1元，5元，10元，20元，50元、100元面值人民币组合给定x元的问题

红太狼 2022-05-12 12:08 205阅读 0赞

最近有一道笔试题引起了小伙伴们的激烈讨论。

### 参考博客 ###

作为算法菜鸟非常感谢大神的分析和举例。[博客地址][Link 1]

### 问题描述 ###

目前市面上的纸币主要有1元，5元，10元，20元，50元、100元六种，如果要买一件商品x元，有多少种货币组成方式？

### 思路一 ###

现有6种面额的纸币用来组合成给定的x元金额。那么可以大致推出这个等式  
sum 表示给定的金额  
\{x1, x2, x3, x4, x5, x6\}分别表示1元，5元，10元，20元，50元、100元的`张数`

s u m = x 1 ∗ 1 + x 2 ∗ 5 + x 3 ∗ 10 + x 4 ∗ 20 + x 5 ∗ 50 + x 6 ∗ 100 sum = x1 \* 1 + x2 \* 5 + x3 \* 10 + x4 \* 20 + x5 \* 50 + x6 \* 100 sum=x1∗1\+x2∗5\+x3∗10\+x4∗20\+x5∗50\+x6∗100

如此看来其实就是求解满足这个等式的 \{x1, x2, x3, x4, x5, x6\} 的所有可能的个数。  
可以通过循环来依次确定每种面额的纸币有多少张，最终来判断，不同张数的组合最终是否等于x元。  
于是有了如下代码：

public class Demo1 { /** * @param x 商品金额 */ public static void test1(int x){ int sum = 0; //符合条件的组合次数 int count = 0; //循环次数 int times = 0; //硬币面额 int[] a = { 1, 5, 10, 20, 50, 100}; for (int i = 0; i <= x / a[5]; i++) { //100元可能出现的张数 for (int j = 0; j <= x / a[4]; j++) { //50元可能出现的张数 for (int k = 0; k <= x / a[3]; k++) { //20元可能出现的张数 for (int l = 0; l <= x / a[2]; l++) { //10元可能出现的张数 for (int m = 0; m <= x / a[1]; m++) { //5元可能出现的张数 //for(int n=0;n<x/1;n++){//这步循环可省略 int n = x - (i * a[5] + j * a[4] + k * a[3] + l * a[2] + m * a[1]); sum = i * a[5] + j * a[4] + k * a[3] + l * a[2] + m * a[1] + n * a[0]; times++; if (sum == x && n >= 0) { count++; } //} } } } } } System.out.println("循环次数：" + times); System.out.println("组合数：" + count); } public static void main(String[] args) { long startTime = System.currentTimeMillis(); //指定200元的金额 test1(200); long endTime = System.currentTimeMillis(); System.out.println("执行时间：" + (endTime - startTime) + "ms"); } }

执行结果如下：

循环次数：142065
    组合数：3274
    执行时间：13ms

#### 结果分析 ####

这种解决方式虽然可以得到正确的结果，但是计算量很大，循环次数随着指定的金额增大会越来越高。性能也就非常差，基本上数字超过1000，就是无脑循环了。所以这并不是最优解。

### 思路二 ###

从上面的分析中我们也可以这么考虑，我们希望用`m`种纸币构成`sum`元。

s u m = x 1 ∗ V 1 + x 2 ∗ V 2 + . . . + x m ∗ V m sum = x1 \* V1 + x2 \* V2 + ... + xm \* Vm sum=x1∗V1\+x2∗V2\+...\+xm∗Vm

根据最后一个面额Vm的系数的取值为无非有这么几种情况，xm分别取｛0, 1, 2, …, sum/Vm｝,换句话说，上面分析中的等式和下面的几个等式的联合是等价的。  
 s u m = x 1 ∗ V 1 + x 2 ∗ V 2 + . . . + 0 ∗ V m sum = x1 \* V1 + x2 \* V2 + ... + 0 \* Vm sum=x1∗V1\+x2∗V2\+...\+0∗Vm

s u m = x 1 ∗ V 1 + x 2 ∗ V 2 + . . . + 1 ∗ V m sum = x1 \* V1 + x2 \* V2 + ... + 1 \* Vm sum=x1∗V1\+x2∗V2\+...\+1∗Vm

s u m = x 1 ∗ V 1 + x 2 ∗ V 2 + . . . + 2 ∗ V m sum = x1 \* V1 + x2 \* V2 + ... + 2 \* Vm sum=x1∗V1\+x2∗V2\+...\+2∗Vm

. . . ... ...

s u m = x 1 ∗ V 1 + x 2 ∗ V 2 + . . . + K ∗ V m sum = x1 \* V1 + x2 \* V2 + ... + K \* Vm sum=x1∗V1\+x2∗V2\+...\+K∗Vm  
其中K是该xm能取的最大数值K = sum / Vm。可是这又有什么用呢？不要急，我们先进行如下变量的定义：

dp\[i\]\[sum\] = 用前i种硬币构成sum 的所有组合数。

那么题目的问题实际上就是求dp\[m\]\[sum\]，即用前m种纸币（所有纸币）构成sum的所有组合数。

在上面的联合等式中：

*  当xm=0时，有多少种组合呢？  
    实际上就是前i-1种纸币组合sum，有dp\[i-1\]\[sum\]种！
 *  xm = 1 时呢，有多少种组合？  
    实际上是用前i-1种纸币组合成(sum - Vm)的组合数，有dp\[i-1\]\[sum -Vm\]种;
 *  xm =2呢， dp\[i-1\]\[sum - 2 \* Vm\]种，等等。

所有的这些情况加起来就是我们的dp\[i\]\[sum\]。所以：

d p \[ i \] \[ s u m \] = d p \[ i − 1 \] \[ s u m − 0 ∗ V m \] + d p \[ i − 1 \] \[ s u m − 1 ∗ V m \] + d p \[ i − 1 \] \[ s u m − 2 ∗ V m \] + . . . + d p \[ i − 1 \] \[ s u m − K ∗ V m \] ; dp\[i\]\[sum\] = dp\[i-1\]\[sum - 0\*Vm\] + dp\[i-1\]\[sum - 1\*Vm\] + dp\[i-1\]\[sum - 2\*Vm\] + ... + dp\[i-1\]\[sum - K\*Vm\]; dp\[i\]\[sum\]=dp\[i−1\]\[sum−0∗Vm\]\+dp\[i−1\]\[sum−1∗Vm\]\+dp\[i−1\]\[sum−2∗Vm\]\+...\+dp\[i−1\]\[sum−K∗Vm\];

其中K = sum / Vm

换一种更抽象的数学描述就是：

d p \[ i \] \[ s u m \] = ∑ k = 0 s u m / v m d p \[ i − 1 \] \[ s u m − K ∗ V m \] dp\[i\]\[sum\] = \\sum\_\{k=0\}^\{sum/vm\} dp\[i-1\]\[sum - K\*Vm\] dp\[i\]\[sum\]=k=0∑sum/vmdp\[i−1\]\[sum−K∗Vm\]

通过此公式，我们可以看到问题被一步步缩小，那么初始情况是什么呢？如果sum=0，那么无论有前多少种来组合0，只有一种可能，就是各个系数都等于0；

dp\[i\]\[0\] = 1 // i = 0, 1, 2, … , m

如果我们用二位数组表示dp\[i\]\[sum\], 我们发现第i行的值全部依赖与i-1行的值，所以我们可以逐行求解该数组。如果前0种纸币要组成sum，我们规定为dp\[0\]\[sum\] = 0.

第二种代码实现方式

public class Demo1 { /** * @param x 商品金额 */ public static void test2(int n){ //纸币面额 int money[]={ 1,5,10,20,50,100}; int dp[] = new int[n+1]; dp[0] = 1; for(int i = 0;i < 6;++i){ for(int j = money[i];j <= n;++j){ dp[j] =(dp[j]+dp[j-money[i]]); } } System.out.println(dp[n]); } public static void main(String[] args) { long startTime = System.currentTimeMillis(); //指定200元的金额 test2(200); long endTime = System.currentTimeMillis(); System.out.println("执行时间：" + (endTime - startTime) + "ms"); } }

执行结果如下

3274
    执行时间：0ms

### 分析 ###

这种思路属于算法中的动态规划。也是动态规划的经典题目。很明显，大大优化了思路一的性能问题。

[Link 1]: https://blog.csdn.net/qiaoqiao0609/article/details/50830992