怎么用Java实现货币组合

本篇内容主要讲解"怎么用Java实现货币组合"，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习"怎么用Java实现货币组合"吧!

给你六种面额 1、5、10、20、50、100 元的纸币，假设每种币值的数量都足够多，编写程序求组成N元（N为0~10000的非负整数）的不同组合的个数。 先分析

1： 假定100和50两种币的和为num， num = 0,50,100,150，... , 50* (N/50)

组合数为 z1 (100x +50y = num 的非负整数解的个数)

2： 20有k张， k=0，1，2，3，.... , (N-num) / 20

3: 那么1，5，10 这几种币的和为 v1andv5andv10 = N- num - 20 * k;

组合数为z2 (10x+5y <= v1andv5andV10的非负整数解的个数)

y<= v1andv5andv10/5-2x 设 m = v1andv5andv10/5；

y<=m; x=0 ;

y<=m-2 ; x=1 ;

y<=m-4； x=2 ;

其实质上就是一个等差数列求和

4: 每趟循环的组合数为 z1 * z2 , 然后求和即为最终的结果。

import java.util.Scanner;public class Main {    public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        System.out.println(getTotal(scanner.nextInt()));    }    private static long getTotal(int money) {        long total = 0L;        for (int num = 0; num <= money; num += 50) {            // 求解 100x + 50y = num  非负整数解的个数  =>   y = num/50 - 2x (x=0,1,2,3...,num/50/2)             int z1 = (num / 50) / 2 + 1;            int v20 = (money - num) / 20;            for (int k = 0; k <= v20; k++) {                // 求解 10x + 5y <= v1andv5andV10  非负整数解的个数                int v1andv5andV10 = money - num - 20 * k;                int tmp = (v1andv5andV10 / 5);                int kkkk = tmp / 2 + 1;                int z2 = (tmp + 1) * kkkk - kkkk * (kkkk - 1);                total = total + (long) (z1) * (long) z2;            }        }        return total;    }}

不用质疑，这是个正确的答案，也是比较容易理解的答案。 内存消耗也应该是最优的，因为没有使用数组，只是使用了几个变量。运行速度也应该还可以， （money/50) * (money/20）/2 次循环运算，100万内的输入应该都是秒出结果。

到此，相信大家对"怎么用Java实现货币组合"有了更深的了解，不妨来实际操作一番吧！这里是网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！