4

我正在尝试使用递归来找到最小数量的硬币来达到给定的数量。我的代码能够列出所需的最少硬币数量，但我似乎找不到打印出用于提出解决方案的硬币的方法。我已经搜索并找到了类似的示例，但我似乎无法正确地将其应用于此。

到目前为止，这是我所拥有的：

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:

如果有人能给我一些关于如何做到这一点的见解，将不胜感激。

4

5 回答 5

2

我认为这应该完全符合您想要实现的目标。只需调用它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;
}
于 2015-10-18T20:34:35.607 回答
0

给你，你有一个测试，功能如下。请注意，不处理边缘情况，例如空货币或负金额。

假设货币数组已排序。如果没有，请使用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;
    }
}

此外，无需使用此方法进行递归；）

于 2015-10-18T20:54:40.327 回答
0

这是一个递归代码（工作，但需要修复......）。这个想法是传递和排列所有硬币 {1,5,10,25,50} 并从左到右递归调用（直到数组结束）

注意事项：

输出中有一个小错误

该数字作为 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;

    }
}
于 2015-10-18T21:00:28.450 回答
0

在您提供的代码中，数字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..]
于 2015-10-19T03:02:13.600 回答
0

我正在做类似的事情，这就是我想出的。您可以将使用过的硬币保存在一个单独的数组中，并使用一个辅助函数递归地打印最后使用过的硬币。如果你想返回一个列表或一个字符串，你可以让助手创建并返回一个。

/**
* FIND MINIMAL NUMBER OF COINS TO MAKE CHANGE, WITH CHANGE VALUES: 1, 2, 5, 10, 20, 50, 100, 200
*
* @param change The amount of change we need to give
* @return Minimal amount of coins used
*/
public static int minimalNumberOfCoinsToMakeChange(int change) {
    int[] denominations = {1, 2, 5, 10, 20, 50, 100, 200};
    int[] dp = new int[change + 1];
    int[] origins = new int[change+1];
    dp[0] = 0;
    for (int i = 1; i <= change; i++) {
        dp[i] = Integer.MAX_VALUE;
        for (int coin : denominations) {
            if (i - coin < 0) {
                continue;
            }
            dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
            origins[i] = coin;
        }
    }
    if (dp[change] == Integer.MAX_VALUE) {
        return -1;
    }
    printPath(origins);
    return dp[change];
}

/**
 * HELPER FUNCTION - GET PATH
 *
 * @param origins Array with origins from main function
 */
private static void printPath(int[] origins) {
    int last = origins[origins.length-1];
    System.out.println(last);
    origins = Arrays.copyOfRange(origins,0,origins.length-last);
    if (origins.length-1 > 0){
        printPath(origins);
    }
}

在此示例中，我对面额数组进行了硬编码，但您应该能够将其删除并将另一个作为参数传递。这不是最有效的方法，但可能对像我这样刚刚进入动态编程的人有所帮助。干杯!

于 2020-12-29T17:04:25.433 回答