find Количество способов получить общее количество 17 центов (например), используя 1,5,10,25,50 центов

Question

Почему я получаю ошибку переполнения стека, и я пытаюсь решить эту проблему рекурсивно как начало, до того, как я начните использовать динамическое программирование. В монете метода «a» - это массив, в котором хранятся монеты, которые будут формировать общую сумму, которую я хочу, сумма - это сумма, которую я хочу (17, например), и i представляет собой индекс массива, который i am at

import java.util.*; 
public class dp2 {//RECURSIVE WAY THEN OPTIMIZE TO DP 
    public static int coins (int [] a, int sum,int i){ 

    if (sum==0) 
     return 1; 
    else if (i==a.length){ 
     return 0; 
    } 
    else if (i>a.length&&sum<a[i]){ 
     return coins(a,sum,i++); 
    } 

    else { 
     return coins(a,sum-a[i],i++)+coins(a,sum-a[i],i); 
    } 
    } 

    public static void main (String [] args){ 
    Scanner sc = new Scanner (System.in); 

    while (sc.hasNext()){ 
     int x = sc.nextInt(); 
     int y=x; 
     int [] a ={1,5,10,25,50}; 
     int w = coins(a,y,0); 
     System.out.println("There are " +w+ " ways to produce "+x + " coins change."); 
    }    
    } 

} 

Answer 1

У вас возникли проблемы с бесконечной петлей.

Сначала проверьте, что вы хотите вернуть, потому что на самом деле вы можете вернуть только 1 или 0. Итак, где другое условие? Пример: i == a.length - 1 или сумма < 0? Думаю, вы хотите вернуть сумму.

А дальше, если вы поместите пример 17, так где же механизм выбрать монеты ведьмы из массива, который вы можете выбрать?

И дальше, пожалуйста, измените return coins(a,sum-a[i],++i)+coins(a,sum-a[i],i);, потому что в вашем коде я всегда 0

Так, может быть, это хороший код exaple для Вас:

class dp2 {//RECURSIVE WAY THEN OPTIMIZE TO DP 
    public static int coins (int [] a, int sum,int i){ 
    if (sum==0) 
     return 1; 
    else if (i==a.length){ 
     return 0; 
    }else if(i + 1 == a.length || sum < 0 || sum - a[i] < 0){ //Your break condition ? 
     return sum; 
    } 
    else if (i>a.length&&sum<a[i]){ 
     return coins(a,sum,i++); 
    } 

    else { 
     return coins(a,sum-a[i],++i)+coins(a,sum-a[i],i); 
    } 
    } 
    public static void main (String [] args){ 
    Scanner sc = new Scanner (System.in); 

    while (sc.hasNext()){ 
     int x = sc.nextInt(); 
     int y=x; 
     int [] a ={1,5,10,25,50}; 
     int w = coins(a,y,0); 
     System.out.println("There are " +w+ " ways to produce "+x + " coins change."); 
    } 
    } 
} 

Answer 2

Я добавил один оператор к коду, в строке 4:

System.out.println(sum + ", " + i); 

Дайте вход 27, выход был:

27, 0 
26, 0 
25, 0 
.... decreasing by one each time... 
3, 0 
2, 0 
1, 0 
0, 0 
-4, 1 
-9, 1 
-14, 1 

И тогда он никогда не останавливается, потому что вы не проверяете sum < 0.

Вы должны быть в состоянии понять это оттуда ... println: самый легкий вес отладчик в мире :-)