java - 更改算法

Question

一个典型的 Change Making 问题，但有点扭曲。给定大量和给定的面额，我需要想出可以使用 RECURSION 制作金额的总数。函数签名如下

int makeChange(int Amount, int[] Denominations)

金额-总金额

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