变更算法

Question

一个典型的变革问题，但有点扭曲。给定大量金额和给定的面额，我需要想出使用 RECURSION 计算金额的全部方法。函数签名如下

int makeChange(int Amount, int[] Denominations)

金额-总金额

面额 - 可用的面额。

它返回方法总数..确保必须使用递归来完成..

Answer 1

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

1. 使用您正在查看的当前硬币，并在从

   amount

   减少它时递归。
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;
}