お手本になるようなソースコード

import java.util.ArrayList;
import java.util.List;

public class Test {

	/**
	 * 札・硬貨の種類 降順であること
	 */
	private static int[] prices = { 10000, 8000, 5000, 1000, 500, 100, 50, 49, 10, 5, 1 };

	/**
	 * 枚数はこれ未満で足りる。
	 */
	private static int[] maxAmounts = new int[prices.length];

	/**
	 * 小銭をかき集めて出来る金額。
	 */
	private static int[] maxCands = new int[prices.length];

	/**
	 * 支払う金額
	 */
	private static int target = 1999999999;

	/**
	 * ある時点で分かっている最小枚数
	 */
	private static int minMai = Integer.MAX_VALUE;

	/**
	 * 最小枚数の結果(複数あることもあるのでリストになっている)
	 */
	private static List<int[]> results = new ArrayList<int[]>();

	/**
	 * 最大公約数 10000 と 8000 ならば 2000
	 * 
	 * @param a
	 * @param b
	 * @return
	 */
	private static int gcd(int a, int b) {
		if (a < b) {
			return gcd(b, a);
		}

		int m = a % b;
		if (m == 0) {
			return b;
		} else {
			return gcd(b, m);
		}
	}

	/**
	 * 最小公倍数 10000 と 8000 ならば 40000
	 * 
	 * @param a
	 * @param b
	 * @return
	 */
	private static int lcm(int a, int b) {
		return (int) ((long) (a * b) / (long) gcd(a, b));
	}

	/**
	 * level 以下(等しいものは含む)の枚数を算出する。
	 * 
	 * @param level
	 * @param amounts
	 * @return
	 */
	private static int calcMai(int level, int[] amounts) {
		int mai = 0;
		for (int i = 0; i <= level; i++) {
			mai += amounts[i];
		}
		return mai;
	}

	/**
	 * level 以下(等しいものは含む)を計算する。
	 * 
	 * @param level
	 * @param amounts
	 * @return
	 */
	private static int calcCand(int level, int[] amounts) {
		int cand = 0;
		for (int i = 0; i <= level; i++) {
			cand += prices[i] * amounts[i];
		}
		return cand;
	}

	/**
	 * level 以下(等しいものは含む)を出力する。
	 * 
	 * @param level
	 * @param amounts
	 */
	private static void output(int level, int[] amounts) {
		String s = "";
		for (int i = 0; i <= level; i++) {
			if (i > 0) {
				s += " + ";
			}
			s += prices[i] + "*" + amounts[i];
		}
		System.out.println(s);
	}

	/**
	 * level 以下(等しいものは含む)をコピーする。
	 * 
	 * @param level
	 * @param amounts
	 * @return
	 */
	private static int[] copyAmounts(int level, int[] amounts) {
		int[] preservedAmounts = new int[prices.length];
		/* 使っている金種の枚数をコピーする。 */
		for (int i = 0; i <= level; i++) {
			preservedAmounts[i] = amounts[i];
		}
		/* 使っていない小さな金種はゼロクリアする。 */
		for (int i = level + 1; i < prices.length; i++) {
			preservedAmounts[i] = 0;
		}
		return preservedAmounts;
	}

	/**
	 * level 以下(等しいものは含む)の中間結果を保存する。 なお、既知の最小枚数より大きければ保存する必要はない。
	 * 
	 * @param level
	 * @param amounts
	 */
	private static void preserve(int level, int[] amounts) {
		int mai = calcMai(level, amounts);
		if (minMai >= mai) {
			if (minMai > mai) {
				minMai = mai;
				results.clear();
			}
			int[] preservedAmounts = copyAmounts(level, amounts);
			results.add(preservedAmounts);
		}
	}

	/**
	 * 金種ごとの最大必要枚数を求める。
	 */
	private static void initMaxAmounts() {
		/* 要素の値が n の場合、a 枚 (a < n) まで使用すれば良い。 */
		for (int i = 1; i < prices.length; i++) {
			int minLcm = Integer.MAX_VALUE;
			for (int j = 0; j < i; j++) {
				int candLcm = lcm(prices[j], prices[i]);
				if (minLcm > candLcm) {
					minLcm = candLcm;
				}
			}
			maxAmounts[i] = minLcm / prices[i];
		}

		/* 最大の金種は枚数に制限がない。 */
		maxAmounts[0] = Integer.MAX_VALUE;
	}

	/**
	 * ある level 以下(等しいものは含む)のすべての金種を、最大必要枚数かき集めて作れる総額を、金種ごとに求める。
	 */
	private static void initMaxCands() {
		int maxCand = 0;
		for (int i = prices.length - 1; i > 0; i--) {
			maxCand += prices[i] * (maxAmounts[i] - 1);
			/* 累計した値を格納する。 */
			maxCands[i] = maxCand;
		}
		/* 最大の金種は総額に制限がない。 */
		maxCands[0] = Integer.MAX_VALUE;
	}

	/**
	 * 再帰メソッド
	 * 
	 * @param level
	 *            ループのネストレベル(0 = もっとも外側(10000円), prices.length - 1 = もっとも内側(1円)
	 * @param amounts
	 *            0 <= index <= level の要素は有効であるが、level < index < prices.length
	 *            の要素は不定な値(ゴミ)として扱う。
	 */
	private static void loop(int level, int[] amounts) {
		for (int i = 0; i < maxAmounts[level]; i++) {
			amounts[level] = i;
			int cand = calcCand(level, amounts);
			if (cand >= target) {
				if (cand == target) {
					preserve(level, amounts);
				}
				break;
			}
			/* これよりさらに内側のループに入ることができるかを調べる。 */
			if (level + 1 < prices.length) {
				/* これより小さい金種まで計算しても無駄ではないかを調べる。 */
				int diff = target - cand;
				if (diff <= maxCands[level + 1]) {
					/* 再帰呼び出しする。 */
					loop(level + 1, amounts);
				}
			}
		}
	}

	/**
	 * メイン
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		/* 金種がちゃんと降順になっているかをチェックする。 */
		for (int i = 1; i < prices.length; i++) {
			if (prices[i - 1] <= prices[i]) {
				throw new IllegalStateException();
			}
		}

		/* 金種ごとの最大必要枚数をあらかじめ求める。 */
		initMaxAmounts();

		/* 金種ごとに最大必要枚数を使って作れる金額をあらかじめ求める。 */
		initMaxCands();

		/* 最大必要枚数を表示する。 */
		for (int i = 0; i < prices.length; i++) {
			System.out.println("" + prices[i] + "円 (最大 (" + maxAmounts[i] + " - 1) 枚必要)");
		}

		/* 支払う総額を表示する。 */
		System.out.println("target = " + target);

		/* ループ変数(金種ごとの枚数) */
		int[] amounts = new int[prices.length];

		/* 再帰メソッドへ突入する。 */
		loop(0, amounts);

		/* 結果を表示する。 */
		System.out.println("最小枚数 = " + minMai);
		for (int[] result : results) {
			output(result.length - 1, result);
		}

		/* 終わりのあいさつをする。 */
		System.out.println("計算終了。");
	}
}

10000円 (最大 (2147483647 - 1) 枚必要)
8000円 (最大 (5 - 1) 枚必要)
5000円 (最大 (2 - 1) 枚必要)
1000円 (最大 (5 - 1) 枚必要)
500円 (最大 (2 - 1) 枚必要)
100円 (最大 (5 - 1) 枚必要)
50円 (最大 (2 - 1) 枚必要)
49円 (最大 (50 - 1) 枚必要)
10円 (最大 (5 - 1) 枚必要)
5円 (最大 (2 - 1) 枚必要)
1円 (最大 (5 - 1) 枚必要)
target = 1999999999
最小枚数 = 200008
10000*199997 + 8000*3 + 5000*1 + 1000*0 + 500*1 + 100*4 + 50*1 + 49*1 + 10*0 + 5*0 + 1*0
10000*199999 + 8000*1 + 5000*0 + 1000*1 + 500*1 + 100*4 + 50*1 + 49*1 + 10*0 + 5*0 + 1*0
計算終了。

    Private 金種リスト As Integer() = {100, 50, 49, 48, 47, 1}
    'Private 金種リスト As Integer() = {10000, 8000, 5000, 1000, 500, 100, 50, 49, 48, 47, 46, 45, 44, 43, 43, 42, 41, 10, 5, 1}
    'Dim 金種リスト As Integer() = {100, 50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 1}
    'Dim 金種リスト As Integer() = {10000, 8000, 5000, 2000, 1000, 500, 100, 50, 10, 5, 1}
    Private 呼び出し回数 As Integer = 0
    Private キャッシュ As New Collections.Generic.Dictionary(Of Integer, Integer())

    Public Function 枚数計算(ByVal 金額 As Integer, Optional ByVal 開始時最適回数 As Integer = Integer.MaxValue, Optional ByVal 開始金種 As Integer = 0) As Integer()
        呼び出し回数 += 1

        ' まずは、キャッシュに計算済みの結果がないか調べる
        If キャッシュ.ContainsKey(金額 * 金種リスト.Length + 開始金種) Then
            Return DirectCast(キャッシュ.Item(金額 * 金種リスト.Length + 開始金種).Clone(), Integer())
        End If

        Dim 最適支払方法 As Integer() = New Integer(金種リスト.Length - 1) {}
        Dim 最適枚数 As Integer = 開始時最適回数
        Dim 今回金種金額 As Integer = 金種リスト(開始金種)
        Dim 今回金種枚数 As Integer

        If 金額 Mod 今回金種金額 = 0 Then
            ' ぴったりだったら、それで OK
            最適支払方法(開始金種) = 金額 \\ 今回金種金額
        Else
            ' ぴったりじゃなかったら、対象金種の多いものから、順に再帰で計算
            For 今回金種枚数 = 金額 \\ 今回金種金額 To 0 Step -1
                Dim 試行金額 As Integer = 金額 - 今回金種金額 * 今回金種枚数

                ' 次の金種で、自明に枚数が大きい場合は、ループ終了
                If (試行金額 \\ 金種リスト(開始金種 + 1)) + 今回金種枚数 > 最適枚数 Then
                    Exit For
                End If

                ' 再帰で、計算をしてみる。
                Dim 試行結果 As Integer() = 枚数計算(試行金額, 最適枚数 - 今回金種枚数, 開始金種 + 1)

                ' 合計枚数を計算
                Dim 試行結果枚数 As Integer = 0
                Dim 枚数 As Integer
                For Each 枚数 In 試行結果
                    試行結果枚数 += 枚数
                Next

                ' 回数が少なかったら、代入( 0 だったら、解なしなので、それはとばす )
                If 試行結果枚数 > 0 AndAlso 最適枚数 > (今回金種枚数 + 試行結果枚数) Then
                    最適支払方法 = 試行結果
                    最適支払方法(開始金種) = 今回金種枚数
                    最適枚数 = 今回金種枚数 + 試行結果枚数
                End If
            Next
        End If

        キャッシュ.Item(金額 * 金種リスト.Length + 開始金種) = DirectCast(最適支払方法.Clone, Integer())
        Return 最適支払方法
    End Function



    Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
        '*** 初期化
        呼び出し回数 = 0
        キャッシュ.Clear()
        Dim t As Integer = Environment.TickCount

        '*** 計算
        Dim 結果 As Integer() = 枚数計算(CInt(TextBox1.Text))

        '*** 統計データ表示
        Console.Write("回数=" & 呼び出し回数.ToString & "  ")
        Console.Write("キャッシュサイズ=" & キャッシュ.Count.ToString & "  ")
        Console.WriteLine("時間=" & (Environment.TickCount - t))

        '*** 結果表示
        Dim sb As New System.Text.StringBuilder
        Dim i As Integer
        sb.Append("( ")
        For i = 0 To 結果.Length - 1
            sb.Append(結果(i).ToString)
            sb.Append(" "c)
        Next
        sb.Append(")")
        Console.WriteLine(sb.ToString)
    End Sub