Java递归硬币更改尝试

Question

我正在尝试Java硬币更改问题以枚举所有可能的更改集。

我的逻辑如下这样：

while n >= denom m { 
array[]+= denom m 
n-= denom m 
} 
list.add[array[]] 

return coinChanger(++denom) 

我的代码：

public List<Integer> makeChange(int change) { 

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

    return changeMaker(change, denominations, 0); 
} 

public List<Integer> changeMaker(int change, int[] denominations, int index) { 
    List<Integer> resultsList = new ArrayList<Integer>(); 
    int[] resultDenom; 
    resultDenom = new int[4]; 

    if (change <= 1) { 
     return resultsList; 
    } 

    while (change >= denominations[index]) { 
     resultDenom[index] += denominations[index]; 
     System.out.println("ResultsDenom: " + resultDenom[index]); 
     change -= denominations[index]; 
    } 
    resultsList.add(resultDenom[index]); 

    for (int val : resultDenom) { 
     System.out.println(val); 
    } 


    if (change > denominations[index]) {  
     return changeMaker(change-=denominations[index], denominations, ++index);  

    } 
    return resultsList; 
} 

该输出仅1组的所有枚举：

OUTPUT：

27 
0 
0 
0 
RESULT CHANGE PERMUTATIONS LIST: [27] 

个

问题：

我竭力要弄清楚如何移动到下一面额，一旦其中一人完成...我知道你应该移到面额数组中的下一个索引...但是那只是增加了下一枚硬币......我如何使它增加下一枚最大的硬币，然后递归地下降到下一枚硬币......一直穿过所有4枚硬币？

谢谢！

* 编辑 **

public List<Integer> makeChange(int change) { 

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

    return changeMaker(change, denominations, 0); 
} 

public List<Integer> changeMaker(int change, int[] denominations, int index) { 
    List<Integer> resultsList = new ArrayList<Integer>(); 
    int[] resultDenom; 
    resultDenom = new int[4]; 

    if (change <= 1) { 
     return resultsList; 
    } 

    if (index > 3) { 
     return resultsList; 
    } 
    //if 27 >= 25 
    if (change >= denominations[index]) { 

     //[+25, 0, 0, 0] 
     resultDenom[index] += denominations[index]; 

     //{ LIST } <--- [25, 0, 0, 0] 
       //List now contains { [25, 0, 0, 0], }, still need all other permutations 
     resultsList.add(resultDenom[index]); 

     //27 - 25, 
     return changeMaker(change-=denominations[index], denominations, ++index);  

    } 
    return resultsList; 
} 

所需的输出：列出清单...... 27美分：

LIST{ [1, 0, 0, 2], [0, 2, 1, 2], [0, 1, 3, 2]... etc}

Answer 1

你的代码似乎为一个有点令人费解您正在尝试解决的问题

尝试实施这一伪码

getChange(int totalCents) 
    { 
     if (totalCents > 25) 
     { 
     print "25"; 
     getChange(totalCents - 25); 
     } 
     else (totalCents > 10) 
     { 
     // same for 10 
     } 
     else (totalCents > 5) 
     { 
     // same for 5 
     } 
     else 
     { 
     // print out number left as pennies 
     } 
    } 

你可以很容易的更换，如果语句与数组索引硬编码值和一个for循环，并与印刷但是你要录制的值。我希望有所帮助。

Answer 2

简单的办法是递归到每一步两个变体（如果你还没有完成）：

1. 继续使用当前的硬币：将它添加到列表和递归。
2. 切换到下一个硬币：增加硬币pos和递归。

应该是这样的：

public class Coins { 
    static final int[] DENOMINATIONS = {25, 10, 5, 1}; 

    public static void change(int amount) { 
    change(amount, new ArrayList<Integer>(), 0); 
    } 

    private static void change(int remaining, List<Integer> coins, int pos) { 
    if (remaining == 0) { 
     System.out.println(coins); 
    } else { 
     if (remaining >= DENOMINATIONS[pos]) { 
     coins.add(DENOMINATIONS[pos]); 
     change(remaining - DENOMINATIONS[pos], coins, pos); 
     coins.remove(coins.size() - 1); 
     } 
     if (pos + 1 < DENOMINATIONS.length) { 
     change(remaining, coins, pos + 1); 
     } 
    } 
    } 
} 

如果你想收集名单，你需要做，其中一个硬币从调用返回后增加（而不是删除它的列表的副本）。