-1

找不到问题，每次我运行这段代码时，由于这条线，它会进入stackoverflow

countCombine += count(array,money - (array[i]*(int)(money/array[i])));

基本上问题很容易。给定一个值 N，如果我们想找 N 美分，并且我们有无限的 S = { S1, S2, .. , Sm} 价值硬币的供应，我们有多少种方法可以找零？硬币的顺序无关紧要。

例如，对于 N = 4 和 S = {1,2,3}，有四种解：{1,1,1,1},{1,1,2},{2,2},{1, 3}。所以输出应该是 4。对于 N = 10 和 S = {2, 5, 3, 6}，有五种解决方案：{2,2,2,2,2}，{2,2,3,3}， {2,2,6}、{2,3,5} 和 {5,5}。所以输出应该是5。

    public class CoinExchangeProblem {

        int countCombine = 0;
        private int count(int array[],int money){
    //        sort the array 
    //        Arrays.sort(array);    
    //        System.out.println(Arrays.toString(array));


            if (money == 0) {
                return 1;
            } else if (money < 0) {
                return 0;
            }


            for(int i = 0; i < array.length; i++){
                countCombine += count(array,money - (array[i]*(int)(money/array[i])));
            }
            return countCombine;

        }




        public static void main(String[] args) {
            CoinExchangeProblem coinExch = new CoinExchangeProblem();
            System.out.println(coinExch.count(new int[]{1,2,3}, 4));
    //        System.out.println(coinExch.count(new int[]{2, 5, 3, 6}, 10));
        }
}
4

1 回答 1

2

当这部分

(array[i]*(int)(money/array[i]))

等于零你是无限递归的受害者，你用相同数量的钱调用函数

您可以将其更改为：

 if(money >= array[i])
        countCombine += count(array,money - (array[i]*(int)(money/array[i])));

所以你永远不会在这里得到零，但是测试它以获得更多示例，因为我没有测试它很多，但我认为它在逻辑上是正确的

于 2013-07-13T03:55:50.783 回答