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); 
     } 
    } 
    } 
} 

如果你想收集名單，你需要做，其中一個硬幣從調用返回後增加（而不是刪除它的列表的副本）。