算法-在java硬币变化

Question

我见过很多硬币更换问题，这个问题很独特。我尝试使用DP和递归，但我无法解决它。

这就是问题所在：

假设给定一个价格，X，其中X是美分，我有5种有限面额的硬币，1,5,10,20,50。我有不同数量的1、5、10、20、50分硬币。我想用最大数量的硬币来确定价格X。我该怎么做？（假设X总是可以用手头的硬币制作）

例如，如果价格X=52，并且

我有三枚一分硬币

我有四枚五分硬币

我有8枚10美分的硬币

我有6枚20美分的硬币

我有4个50美分的硬币

我想找出最大数量的硬币，以及可以用来定价的方法，在这种情况下：两枚1美分、四枚5美分、三枚10美分的硬币就是答案。

我想到了一个可用的算法，首先，我将每个硬币的数量和值放入arraylist，然后将数组列表传递到一个递归函数中，该函数将：

首先，扣除最小面额的价格，然后将1加到int max，其中max=当前使用的硬币数量。然后，递归调用价格=价格-最小面额的函数。

其次，我将通过取下一个最小的可用面额递归调用该函数。

我的基本情况是如果

1) price <0, return 0

2) if price ==0 and max=currMax,  return 1

3) if price>0, recursively call the 2 recursions listed above

编辑：添加代码。

我稍微修改了一下这个问题。

  1 import java.util.*;
  2 public class CountingChange{
  3     int max = 0; //maximum number of way to pay price
  4     int way = 0; //number of ways to make price
  5     private void run(){
  6         Scanner sc = new Scanner(System.in);
  7         int price = sc.nextInt();
  8         ArrayList<Integer> coins = new ArrayList<Integer>(); //kinds of coins. assumed to be 1,5,10,20,50
  9         for (int i = 0; i <5; i++){
 10             int coin = sc.nextInt();
 11             coins.add(i,coin);
 12         }
 13         int currMax = 0;
 14         counter(price,coins,currMax);
 15         System.out.println(String.valueOf(max) + " " + String.valueOf(way)); //output eg: 10 5, where 10 = max coins, 5 = ways
 16     }
 17     private void counter(int price,ArrayList<Integer> coins,int currMax){
 18         currMax += 1;
 19         if (coins.size()==0) return;             
              else if((coins.get(0)<0)||(price<0)){
 20             //check if AL is empty(no way to make change), smallest coin < 0(invalid), price<0(invalid)
 21             return;
 22         }
 23         else if (price==0){//successful change made
 24             if (currMax==max){ //check max coins used
 25                 way+=1;
 26             }
 27             else if (currMax>max){
 28                 way = 1;
 29                 max = currMax;
 30             }
 31         }
 32         else if(price>0){
 33             coins.set(0,coins.get(0)-1);//use smallest coin
 34             counter(price-coins.get(0),coins,currMax);
 35             coins.remove(0);//use other coins except smallest
 36             counter(price,coins,currMax);
 37         }
 38     }
 39     public static void main(String[] args){
 40         CountingChange myCountingChange = new CountingChange();
 41         myCountingChange.run();
 42     }
 43 }

我认为我的问题是，我是在扣除用于定价的硬币数量（而不是硬币的价值）。但我真的不知道如何使用合适的//什么样的数据结构来存储我的硬币及其价值。

Answer 1

您可以使用一个列表来跟踪在递归的每个点添加了哪些硬币。使用第二个列表跟踪当前最大解决方案。当你找到一个解决方案时，检查它是否有超过当前最大值的硬币。

下面是一些Java代码来说明：

public static void main(String[] args)
{
    int[] values = { 1, 5, 10, 20, 50 };
    int[] available = { 3, 4, 8, 6, 4 };
    int change = 52;
    List<Integer> maxCoins = new ArrayList<>();
    LinkedList<Integer> coins = new LinkedList<>();

    maxCoins(0, change, values, available, maxCoins, coins);

    System.out.println(maxCoins);
}

public static void maxCoins(int pos, int change, int[] values, int[] available, List<Integer> maxCoins, LinkedList<Integer> coins)
{
    if (change == 0)
    {
        if (maxCoins.isEmpty() || maxCoins.size() < coins.size())
        {
            maxCoins.clear();
            maxCoins.addAll(coins);
        }
    } 
    else if (change < 0)
    {
        return;
    }

    for (int i = pos; i < values.length && values[i] <= change; i++)
    {
        if (available[i] > 0)
        {
            available[i]--;
            coins.addLast(values[i]);
            maxCoins(i, change - values[i], values, available, maxCoins, coins);
            coins.removeLast();
            available[i]++;
        }
    }
}

输出：

[1, 1, 5, 5, 5, 5, 10, 10, 10]