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

import java.util.*;

public class Test {
	
	/**
	 * 札・硬貨の種類
	 * 降順であること
	 */
	private static int[] prices = {10000, 8000, 5000, 1000, 500, 100, 50, 10, 5, 1};
	
	/**
	 * 支払う金額
	 */
	private static int target = 63999;

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

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

	/**
	 * 枚数を算出する。
	 * 
	 * @param amounts
	 * @return
	 */
	private static int calcMai(int[] amounts) {
		int mai = 0;
		for (int i = 0; i < amounts.length; 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 clearAmounts(int level, int[] amounts) {
		for (int i = level; i < amounts.length; i++) {
			amounts[i] = 0;
		}
	}

	/**
	 * この level で、この amount の場合、 これより小さい(上位層)の level に両替(まとめることが)できるか。
	 * 
	 * @param level
	 * @param amount
	 * @return
	 */
	private static boolean isExchangeable(int level, int amount) {
		if (amount == 0) {
			return false;
		}

		int total = prices[level] * amount;
		for (int i = 0; i < level; i++) {
			if (total % prices[i] == 0) {
				return true;
			}
		}
		return false;
	}

	/**
	 * 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);
	}

	/**
	 * つぎのループ変数を算出する。
	 * 
	 * @param level
	 * @param amounts
	 * @return
	 */
	private static int nextLevel(int level, int[] amounts) {
		int cand = calcCand(level, amounts);
		int diff = target - cand;
		/* 除算は切り捨て*/
		int inc = diff / prices[level];
		if (inc == 0) {
			if (level + 1 < prices.length) {
				level++;
			} else {
				amounts[level] += 1;
			}
		} else {
			if (isExchangeable(level, amounts[level])) {
				amounts[level] += inc;
			} else {
				if (level + 1 < prices.length) {
					level++;
				} else {
					amounts[level] += inc;
				}
			}
		}
		return level;
	}

	/**
	 * 中間結果を保存する。
	 * なお、既知の最小枚数より大きければ保存する必要はない。
	 * 
	 * @param amounts
	 */
	private static void preserve(int[] amounts) {
		int mai = calcMai(amounts);
		if (minMai >= mai) {
			if (minMai > mai) {
				minMai = mai;
				results.clear();
			}
			results.add((int[]) (amounts.clone()));
		}
	}
	
	/**
	 * メイン
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		int[] amounts = new int[prices.length];
		clearAmounts(0, amounts);

		/* ループのネストレベル(0 = もっとも外側(10000円), prices.length - 1 = もっとも内側(1円) */
		int level = 0;
		/* 試行したループ回数(参考のためだけ) */
		long count = 0;
		while (true) {
			count++;
			int cand = calcCand(level, amounts);
			if (cand >= target) {
				if (cand == target) {
					preserve(amounts);
				}
				level--;
				if (level < 0) {
					break;
				}
				clearAmounts(level + 1, amounts);
				amounts[level] += 1;
			} else {
				level = nextLevel(level, amounts);
			}
		}
	
		System.out.println("loop count = " + count);
		System.out.println("target = " + target);
		for (int[] result : results) {
			output(result.length - 1, result);
		}
	}
}

import java.util.ArrayList;

import java.util.Arrays;

import java.util.HashMap;

import java.util.List;



/**

 * 金種計算 Ver.2

 */

public class Sample2 {

  // 金種定義

  static final int[] unit = {

      1, 5, 10, 50, 100, 500, 1000, 5000, 8000, 10000,

  };



  /**

   * 金額を表現する実際の金種枚数を保持するクラス

   */

  static class Amount {

    int[] counts = new int[unit.length]; // 各金種の使用枚数

    int sum = 0; // 実際の金額



    public Amount() {

      // 金額0

    }



    // コピーコンストラクタ (一応)

    public Amount(Amount other) {

      copyFromOther(other);

    }



    // 元の金額に1枚追加した状態を作成

    public Amount(Amount base, int addIndex) {

      copyFromOther(base);

      this.counts[addIndex]++;

      this.sum += unit[addIndex];

    }



    // ほかのAmountオブジェクトから内容をコピー

    private void copyFromOther(Amount other) {

      System.arraycopy(other.counts, 0, this.counts, 0, unit.length);

      this.sum = other.sum;

    }



    // 金額はいくら ?

    public int getValue() {

      return sum;

    }



    // HashMap管理用ハッシュコード...金額がユニークなんだし、これでいいよね

    public int hashCode() {

      return sum;

    }



    // 同値判定用

    public boolean equals(Object o) {

      Amount other = (Amount) o;

      return this.sum == other.sum;

    }



    // 結果出力用

    public String toString() {

      StringBuilder sb = new StringBuilder();

      for (int i = 0; i < unit.length; i++) {

        sb.append(unit[i] + " : " + counts[i] + "\n");

      }

      return sb.toString();

    }

  }



  /**

   * main()

   */

  public static void main(String[] args) {

    final int goal = Integer.parseInt(args[0]); // 表現したい金額



    HashMap<Integer, Amount> hashMap = new HashMap<Integer, Amount>(); // HashMapで管理

    // key: 金額, value: 表現状態

    

    // 初期状態: 金額0 のものを入れておく

    hashMap.put(0, new Amount());



    while (true) { // 見つかるまでループ

      List<Amount> list = new ArrayList<Amount>(); // 「n枚」で実現できるものを一時保管 → 後で一括追加



      for (int key : hashMap.keySet()) {   // 「n-1枚まで」で実現できる組み合わせでループ

        Amount baseValue = hashMap.get(key);



        for (int i = 0; i < unit.length; i++) {

          Amount value = new Amount(baseValue, i); // n枚目を足した状態

          

          if (hashMap.containsKey(value.getValue())) { // 既出ならスキップ

            continue;

          }

          

          if (value.getValue() == goal) { // 解答発見 -> 表示して終了

            System.out.println(value.toString());

            System.exit(0);

          }

          

          list.add(value);

        }

      }

      

      // 「n-1枚まで」で実現できるもの + 「n枚」で実現できるもの == 「n枚まで」で実現できるもの

      for (Amount value : list) {

        hashMap.put(value.getValue(), value);

      }

    }

  }

}

        Dim 金種リスト As Integer() = {10000, 8000, 5000, 2000, 1000, 500, 100, 50, 10, 5, 1}
        Dim 最適支払方法 As Integer() = New Integer(金種リスト.Length - 1) {}
        Dim 開始金種 As Integer = 0
        Dim 試行金額 As Integer = 0
        Dim 金額 As Integer = Integer.Parse(txtIn.Text)
        Dim 最適枚数 As Integer = Integer.MaxValue
        '        Dim 結果 As New StringBuilder

        ' 開始する金種を決定
        For i As Integer = 0 To 金種リスト.Length - 1
            If 金額 >= 金種リスト(i) Then
                開始金種 = i
                Exit For
            End If
        Next

        ' 開始金種の大きい枚数から順にチェック
        For i As Integer = 金額 ￥ 金種リスト(開始金種) To 0 Step -1
            Dim 支払方法 As Integer() = New Integer(金種リスト.Length - 1) {}
            Dim 枚数 As Integer = 0

            試行金額 = 金額 - 金種リスト(開始金種) * i
            枚数 += i
            支払方法(開始金種) = i
            '            結果.Append(金種リスト(開始金種) & "円×" & i & "枚、")

            ' 割り切れたら、即終了
            If 試行金額 = 0 Then
                最適枚数 = 枚数
                最適支払方法 = 支払方法
                Exit For
            End If

            ' 金種を順にチェックしていく
            For j As Integer = 開始金種 + 1 To 金種リスト.Length - 1
                Dim k As Integer = 試行金額 ￥ 金種リスト(j)

                試行金額 = 試行金額 - 金種リスト(j) * k
                枚数 += k
                支払方法(j) = k
                '                結果.Append(金種リスト(j) & "円×" & k & "枚、")

                ' 割り切れたら、終了
                If 試行金額 = 0 Then
                    Exit For
                End If
            Next

            If 枚数 < 最適枚数 Then
                最適枚数 = 枚数
                最適支払方法 = 支払方法
            End If
        Next