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

import java.util.*;

/**
 * 第一引数が0以上の整数であれば、 
 * その表す金額を日本円で現金化したときに、 
 * その枚数が最小となる紙幣と硬貨の組み合わせを、 
 * 標準出力に出力するコンソールアプリケーションを作ってください。 
 */
public class Test {
    /**
     * メイン.
     */
    public static void main(String[] args) 
    {
        if (1 >= args.length) {
            System.out.println("java Test [金額] [紙幣1] [紙幣2] ...");
            System.out.println("金額を表現する紙幣で枚数が最小となるものを求める");
            return;
        }
        int sum = Integer.parseInt(args[0], 10);
        int[] units = new int[args.length-1];
        for (int i=0;i<units.length;i++) {
            units[i] = Integer.parseInt(args[i+1], 10);
        }
        int[] result = searchResult(sum, units);
        if (result==null) System.out.println("この金額は表現できません");
        else {
            System.out.print("金額:" + sum + " = ");
            for (int i=0;i<units.length;i++) {
                if (i>0) System.out.print(" + ");
                System.out.print(units[i]);
                System.out.print(" * " + result[i]);
            }
            System.out.println();
        }
    }

    /**
     * 最小枚数を求める
     * 単純にサーチすると硬貨種類のべき乗でサーチパスが
     * 爆発するので、有効なパスだけを記録して更新することにする
     * 
     * @param sum 総和となる金額
     * @param units 紙幣(硬貨)の単位
     */
    public static int[] searchResult(int sum, int[] units)
    {
        // 1つ前の長さのパスで有効なものの情報を記録する
        // Mapのkeyは硬貨枚数の配列で,valueはその総和
        // スピードはあまり気にしてない
        Map<int[], Integer> prev = new HashMap<int[], Integer>();
        int[] start = new int[units.length]; // すべて0の開始状態
        prev.put(start, 0);
        for (int n=1; ;n++) {  // nは枚数
            // 長さnのパスに対する金額を求める
            Map<int[], Integer> next = new HashMap<int[], Integer>();
            boolean any = false;
            for (Iterator<Map.Entry<int[], Integer>> iter=prev.entrySet().iterator(); iter.hasNext(); ) {
                Map.Entry<int[], Integer> entry = iter.next();
                int[] key = entry.getKey();
                int value = entry.getValue();
                for (int i=0;i<units.length;i++) {
                    int nextsum = value + units[i];
                    if (nextsum==sum) {
                        // 見つかった
                        key[i]++;
                        return(key);
                    }
                    else if (nextsum < sum) {
                        // 経路途中候補
                        int[] nextkey = new int[units.length];
                        for (int j=0;j<units.length;j++) nextkey[j] = key[j];
                        nextkey[i]++;
                        next.put(nextkey, nextsum);  // 重複しても1つ
                        any = true;
                    }
                }
            }
            // 候補がなくなれば表現できない金額だった
            if (!any) return(null);
            // 結果を記録
            prev = next;
        }
    }
}

    Private 金種リスト As Integer() = {10000, 8000, 1000, 500, 100, 50, 10, 5, 1}

    Public Function 枚数計算(ByVal 金額 As Integer, Optional ByVal 開始金種 As Integer = 0) As Integer()
        Dim 最適支払方法 As Integer() = New Integer(金種リスト.Length - 1) {}
        Dim 最適枚数 As Integer = Integer.MaxValue
        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

                ' 回数が少なかったら、代入
                If 最適枚数 > (今回金種枚数 + 試行結果枚数) Then
                    最適支払方法 = 試行結果
                    最適支払方法(開始金種) = 今回金種枚数
                    最適枚数 = 今回金種枚数 + 試行結果枚数
                End If
            Next
        End If
        Return 最適支払方法
    End Function

class Program
{
    static void Main(string[] args)
    {
        Money m10000 = new Money(10000);
        Money m5000 = new Money(5000);
        Money m1000 = new Money(1000);
        Money m500 = new Money(500);
        Money m100 = new Money(100);
        Money m50 = new Money(50);
        Money m10 = new Money(10);
        Money m5 = new Money(5);
        Money m1 = new Money(1);

        m10000.Next += new NextEventHandler(m5000.Calculate);
        m5000.Next += new NextEventHandler(m1000.Calculate);
        m1000.Next += new NextEventHandler(m500.Calculate);
        m500.Next += new NextEventHandler(m100.Calculate);
        m100.Next += new NextEventHandler(m50.Calculate);
        m50.Next += new NextEventHandler(m10.Calculate);
        m10.Next += new NextEventHandler(m5.Calculate);
        m5.Next += new NextEventHandler(m1.Calculate);

        string temp = Console.ReadLine();
        int input = int.Parse(temp);
        Console.WriteLine(input.ToString("#,##0") + " : ");
        m10000.Calculate(input);
    }
}

class Money
{
    public event NextEventHandler Next;

    public Money(int amount)
    {
        this.Amount = amount;
    }

    public readonly int Amount;

    public void Calculate(int amount)
    {
        int restAmount = amount;
        int count = 0;

        while (restAmount >= this.Amount)
        {
            restAmount -= this.Amount;
            count++;
        }

        Console.WriteLine(this.Amount.ToString("#,##0").PadLeft(6, ' ') + " * " + count);

        if (this.Next != null)
        {
            this.Next(restAmount);
        }
    }
}

delegate void NextEventHandler(int restAmont);