确定将一定数量的钱比如100，换成1，2，5，10，20，50的组合问题集锦

1、最霸道的解法，估计一般的码农是看不懂了。。。。

package test;

import java.util.Arrays;

public class CoinToSum1 {
	public static void main(String[] args) {
		int[] a = new int[] { 1, 2, 5, 10, 20, 50 };
		int[] b = new int[101];
		int[] c = new int[101];

		System.out.println(System.currentTimeMillis());
		Arrays.fill(b, 1);
		for (int i = 1; i < a.length; i++) {
			for (int j = 1; j * a[i] <= 100; j++) {
				for (int k = 0; k + j * a[i] <= 100; k++)
					c[k + j * a[i]] += b[k];

			}
			for (int k = 1; k <= 100; k++) {
				b[k] += c[k];
				c[k] = 0;
			}
		}
		System.out.println("totally " + b[100] + " solutions.");
		System.out.println(System.currentTimeMillis());//0 ms
	}
}

这个最给力，号称什么“母函数法”，消耗时间几乎为 0ms!

2、常用的递归解法

package test;

public class CoinToSum2 {
	private static final int[] COINS = new int[] { 1, 2, 5, 10, 20, 50 };

	private static final int SUM = 100;

	private static int cnt = 0;

	public static void main(String[] args) {
		System.out.println(System.currentTimeMillis());
		calc(0, 0, "");
		System.out.println("total " + cnt + " solutions. ");
		System.out.println(System.currentTimeMillis());// 110 ms
	}

	private static void calc(int sum, int coinIndex, String pre) {
		if (SUM == sum) {
			++cnt;
		}

		for (int i = coinIndex; i < COINS.length; i++) {
			if (SUM - sum >= 0) {
				calc(sum + COINS[i], i, pre + " " + COINS[i]);
			}
		}
	}
}

这个消耗时间大概在110ms,比第1个逊色多了。。。而且代码晦涩难懂、不好理解

3、在第2个的基础上稍微优化了点，减少了递归次数

package test;

public class CoinToSum3 {
	private static final int[] COINS = new int[] { 1, 2, 5, 10, 20, 50 };

	private static int count = 0;

	public static void main(String[] args) throws Exception {
		System.out.println(System.currentTimeMillis());
		calc(100, 5, "");
		System.out.println("totally " + count + " solutions. ");
		System.out.println(System.currentTimeMillis());// 50ms
	}

	private static void calc(int sum, int coinIdex, String pre) {
		if (sum <= 0) {
			if (sum == 0) {
				count++;
			}
		}
		for (int i = coinIdex; i >= 0; i--) {
			if (sum >= 0) {
				calc(sum - COINS[i], i, pre + " " + COINS[i]);
			}
		}
	}
}

这个消耗时间大概在50ms,比第2个在性能上提升了近1倍，不过二者的原理是一样的。

4、不用递归，改用栈，某人自己写了个方法 由于篇幅太长，就不拿出来丢人现眼了...
这个大概耗时80ms,只能说一般而已。

代码附上：CoinToSum.rar，见附件！

楼主能不能给点注释啊！  本人很学学习，但是看不懂，希望给点注释，同时能够输出每一种组合的具体情况(比如第一种方案是由 1 1 1 20 50。。。)谢谢了