变更算法

Question

一个典型的变革问题，但有点扭曲。给定一个大的金额和面额，我需要想出总数的方式，其中金额可以使用RECURSION。函数的签名如下

int makeChange（int Amount， int[]面额）

总数

面额-可用面额。

Answer 1

关键是要了解在每一点上，你有两个选择：

1. 使用您正在查看的当前硬币，并在将其从金额减少时递归
2. 不要使用它，并使其在以后选择时不可用

函数应该返回（1）和（2）的总和。

伪代码：

makeChange(amount,Denominations):
   //stop clauses:
   if (amount == 0) return 1
   if (amount < 0) return 0
   i <- first index of Denominations where Denominations[i] is not zero
   if there is no such i (all are zero):
        return 0
   num1 = makeChange(amount-Denominations[i],Denominations) //recursive call, using Denominations[i]
   temp <- Denominations[i]
   Denominations[i] = 0
   num2 = makeChange(amount,Denominations) //recursive call, not using Denominations[i] - and will never do again
   Denominations[i] = temp //setting environment back to original
   return num1+num2

java代码：

public static int makeChange(int amount, int[] d) { 
    if (amount < 0) return 0;
    if (amount == 0) return 1;
    int i = 0;
    for (i = 0; i < d.length; i++) { 
        if (d[i] != 0) break;
    }
    if (i == d.length) return 0;
    int num1 = makeChange(amount-d[i],d);
    int temp = d[i];
    d[i] = 0;
    int num2 = makeChange(amount,d);
    d[i] = temp;
    return num1 + num2;
}