0

在这里，我正在解决以下问题，其中给定 n 种硬币面额的值v(1) > v(2) > ... > v(n) (all integers)
以下代码试图找到进行 sum-C 所需的最小硬币数量。这里的 C 是 100（见 main 函数）。当我运行代码时，错误——“java.lang.StackOverflowError”来了。请帮忙。

import java.util.ArrayList;

public class Problem2 {

    public static int count=4;
    public static int []v={25,10,5,1}; //Array storing denominations

    private static int findminimum(ArrayList<Integer> v2) {

        int count=v2.get(0);
        for(int i=0;i<v2.size();i++)
        {
            if(count>v2.get(i))
            {
                count=v2.get(i);
            }
        }
        return count;
    }

    public static int countmincoins(int n)
    {
        int t;
        if(n<0)
        {
            t=Integer.MAX_VALUE-100 ;
        }
        if(n==0)
        {
            t= 0;
        }
        else
        {
            ArrayList<Integer> a=new ArrayList<Integer>();          
            for(int i=0;i<v.length;i++)
            {
                int temp=0;
                temp=countmincoins(n-v[i])+1; //Stackoverflow error
                a.add(temp);    
            }   
            t=findminimum(a);

        } 
        return t;   
    }


    public static void main(String args[])
    {

        System.out.println(countmincoins(100)); 
    }
}
4

3 回答 3

0

如果您不限于使用递归，则以下内容会简单得多：

public static int[] denominations = {25,10,5,1};

public static int minimumCoins(int amount){
    int total = 0;
    for(int denomination: denominations){
        while(amount - denomination >= 0){
            amount -= denomination;
            total++;
        }
    }
    return total;
}

public static void main(String args[])
{

    System.out.println(minimumCoins(98)); 
}
于 2013-07-01T09:00:05.377 回答
0

如果你使用递归，那么你需要达到一个条件来终止递归。但是在您的代码中，我没有看到任何终止逻辑。这就是为什么，它会进入无限循环和 StackOverflowException。在您的代码中，您使用以下代码终止。

if(n==0)
{
    t= 0;
}

但这里的 n 可能不为零。因为countmincoins(n-v[i])不要确保你的 n 会是 0。

于 2013-07-01T09:08:46.253 回答
0

您的代码是无限的，因为t永远不会<0 or ==0给出数组和条件(n - v[i] )+1中 v[i]的值，在每次调用该方法时总是返回相同的值，因此是无限递归。

于 2013-07-01T09:17:29.353 回答