銅貨を両替する

銅貨を両替する

下図のように、多単位硬貨の場合、小銭を最小限の硬貨に両替するにはどうすればいいですか?
単位硬貨ごとに無限に使用できます.

説明の入力

1行目はコインの種類数N(1<=N<=12)を与える.2行目にはN個のコインの種類が与えられ、
次の行では、検索する金額M(1<=M<=500)が与えられます.コインの種類は100元を超えない.

出力の説明

最初の行に探しているコインの最小個数を出力します.

入力

3
1 2 5
15

しゅつりょく

3

ヒント

出力説明:5 5 5 5 5硬貨3個、探せます.

誤った実装コード

public class 동전교환 {
    static int n;
    static int m;
    static int[] coins;
    static int answer = Integer.MAX_VALUE;

    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt(); //동전 종류 개수
        coins = new int[n];
        for (int i = 0; i < n; i++) {
            coins[i] = in.nextInt();
        }
        m = in.nextInt(); //거슬러줄 금액

        dfs(0, m, 0);
        System.out.println(answer);

    }

    //    static void dfs(int i, int sum, int count){
//        System.out.println("sum: "+sum);
//        if(sum==m && count<=answer){
//            answer = count;
//            return;
//        }
//        else{
//            if(i==3) i = 0;
//            dfs(i+1,sum+coins[i],count+1);
//            dfs(i+1,sum,count);
//        }
//    }

    static void dfs(int i, int sum, int count) {
        System.out.println("sum :"+sum+" count: "+count);
        if(sum<0) return;
        if (sum == 0 && count <= answer) {
            answer = count;
            return;
        } else {
            if (i == 3) i = 0;
            dfs(i + 1, sum - coins[i], count + 1);
            dfs(i + 1, sum, count);
        }
    }
}

最初に考えられた方法は,再帰呼び出しによりsumにコイン金額を加算するか,加算しないでindexを徐々に高め,再帰呼び出しにより実現する.2つ目は、合計からコインを減算し、sumで0、countで最小時間に戻る2つのケースを連続的に呼び出すことです.上述したように、javaは無限の再帰呼び出しによって呼び出される.lang.StackOverflowErrorが発生しました.

ベストアンサーを参考にした実装コード

 static int n;
    static int m;
    static int[] coins;
    static int answer = Integer.MAX_VALUE;

    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt(); //동전 종류 개수
        coins = new int[n];
        for (int i = 0; i < n; i++) {
            coins[i] = in.nextInt();
        }
        m = in.nextInt(); //거슬러줄 금액

        dfs(0,0);
        System.out.println(answer);

    }


    static void dfs(int L,int sum){
        //L: 동전의 개수
        //sum: L개 동전 금액의 총합
        if(L>=answer) return;
        if(sum>m) return; //무한 안돌려면 이게 필요
        if(sum==m){
            answer = Math.min(L,answer);
        }
        else {
            for (int i = n-1; i >= 0; i--) {
                dfs(L + 1, sum + coins[i]);
            }
        }
    }

基本的な考え方自体に違いはありませんが、停止の条件には達していません.sum>mの場合は停止しなければならず、コイン数が答えより大きい場合はこれ以上見る必要はないので停止しなければならない.