打印哪些硬幣用於製作給定數量

Question

我正在嘗試使用遞歸來查找製作給定數量的最小硬幣數量。我有能夠列出所需硬幣最小數量的代碼，但我似乎無法找到打印出使用哪個硬幣來提供解決方案的方法。我搜索並找到了類似的例子，但我似乎無法正確地將其應用於此。

這裏是我迄今：

import java.util.*; 

public class Coins{ 

    public static int findMinCoins(int[] currency, int amount) { 
     int i, j, min, tempSolution; 

     min = amount; 

     for (i = 0; i < currency.length; i++) { 
      if (currency[i] == amount) { 
       return 1; 
      } 
     } 

     for (j = 1; j <= (amount/2); j++) { 
      tempSolution = findMinCoins(currency, j) + findMinCoins(currency, amount - j); 
      if (tempSolution < min) { 
       min = tempSolution; 
      } 
     } 
     return min; 
    } 

    public static void main(String[] args) { 
     Scanner in = new Scanner(System.in); 
     int[] USA = 
     {1, 5, 10, 25, 50}; 
     System.out.println("Please enter an integer amount."); 
     int amount = in.nextInt(); 
     int minCoins = findMinCoins(USA, amount); 
     System.out.println("The minimum number of coins to make " + amount + " in United States currency is " + minCoins + "."); 
     System.out.println("The coins used were:"); 
     /*Print coins used to find minCoins.*/ 
     in.close(); 
    } 
} 

代碼運行至今的一個例子：

Please enter an integer amount. 
17 
The minimum number of coins to make 17 in United States currency is 4. 
The coins used were: 

如果有人可以給我如何做到這一點一些見解，它會非常感謝。

Answer 1

我認爲這應該完全符合您的要求。只需撥打public static int findMinCoins(arg1, arg2)和它就會使用遞歸算法爲您輸出最小數量的硬幣和所有特定硬幣（它會顯示其出現次數）。

public static int findMinCoins(int[] currency, int amount) { 
    int min = findMinCoins(currency, amount, 0); 
    System.out.print("The coins used were: "); 
    return min; 
} 
private static int findMinCoins(int[] currency, int amount, int min){ 
    int number, value1, value2; 
    int min1 = min; 
    for(int i=currency.length-1; i>=0; i--) { 
     if (amount>=currency[i]){ 
      amount = amount - currency[i]; 
      System.out.print(currency[i] + " "); 
      min1 = findMinCoins(currency, amount, min1); 
      return ++min1; 
     } 
    } 
    return min1; 
} 

Answer 2

在這裏，你有一個測試，功能如下。請注意，未處理邊緣案例，例如空貨幣或負數。

假定貨幣數組已排序。如果不是，則用Arrays.sort(currency)進行分類。

public class FindMinimumCoinsTest { 

    @Test 
    public void test() throws Exception { 
     int[] USA = { 1, 5, 10, 25, 50 }; 
     assertEquals(2, findMinCoins(USA, 11)); 
     assertEquals(4, findMinCoins(USA, 8)); 
     assertEquals(4, findMinCoins(USA, 111)); 
     assertEquals(3, findMinCoins(USA, 27)); 
    } 

    public static int findMinCoins(int[] currency, int amount) { 
     int coins = 0; 
     int sum = 0; 
     int value, n; 

     for (int i = currency.length - 1; i >= 0; i--) { 
      value = currency[i]; 
      n = (amount - sum)/value; 
      if (n > 0) { 
       coins += n; 
       sum += n * value; 
      } 
     } 
     return coins; 
    } 
} 

而且，沒有必要使用此方法遞歸;）

Answer 3

這裏是一個遞歸碼（工作，但需要一個修復...）。 的想法是通過，並與所有硬幣{1,5,10,25,50}和遞歸調用陣列從左至右（直到陣列的端部）

NOTES：

有一個小錯誤在輸出中

該數字以1個元素的數組而不是基元int的形式傳遞。 （這是爲了有一個引用類型通過所有的遞歸調用，以保持它的價值：

public class coins { 

    public static void main(String[] args) { 
     // arrays of coin types 
     int[] coinTypes = { 0, 1, 5, 10, 25, 50 }; 
     // arrays are references, so changing them 
     // inside the recursive function will 'really' change 
     int[] price = {11}; // sample input 
     tryBigger(price, coinTypes, 0); 
    } 

    // tries to see if higher coin is possible by passing array 
    // of coin types and recursively call until the end of array 
    public static void tryBigger(int[] price, int[] theCoins, int index) { 
     if (index < theCoins.length-1){ 
      // until last element 
      if (price[0] > theCoins[index]){ 
       tryBigger(price, theCoins, ++index); 
      } 
     } 
     // find amount of this coin 
     int thisCoin = price[0]/theCoins[index]; 
     // remove the amount already got before 
     price[0] = price[0] - thisCoin*theCoins[index]; 
     System.out.println(thisCoin + " coins of " + theCoins[index]); 
     return; 

    } 
} 

Answer 4

在您提供的代碼，無論是數量1或min由遞歸函數返回用這種方法保持一致，單向你可以獲得硬幣列表是通過改變返回變量來包括硬幣和計數

下面是一個總體思想的例子;因爲我不知道Java編程，所以我將把實現留給你。

if (currency[i] == amount){ 
    return [1,i]; 

... 

temp1 = findMinCoins(currency,j); 
temp2 = findMinCoins(currency,amount - j); 

if(temp1[0] + temp2[0] < min[0]){ 
    min = [temp1[0] + temp2[0]] concatenated with temp1[1..] and temp2[1..]