打印使用哪些硬币来赚取给定数量

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} 并从左到右递归调用（直到数组结束）

备注：

输出中有一个小错误

该数字作为 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 由递归函数 return 编辑。按照这种方法，获取硬币列表的一种方法是更改 return 变量以包含硬币和计数。

这是一个总体思路的例子；因为我不知道 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..]

Answer 5

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

/**
* 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);
    }
}

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

打印使用哪些硬币来赚取给定数量

Printing which coins are used to make a given amount

java

algorithm

recursion

coin-change