算法 - java中的硬币变化-Java 学习之路

我看到了很多硬币更换问题，这个问题非常独特 . 我尝试使用DP和递归，但我无法解决它 .

这就是问题：

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

例如，如果价格X = 52和

我有3分1美分硬币

我有4美分的5美分硬币

我有8个10美分硬币

我有6个20美分硬币

我有4个50美分硬币

我想找到最大数量的硬币和可以用来制作这个价格的方式，在这种情况下：两个1美分，4个5美分，3个10美分硬币将是答案 .

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

首先，用最小面额扣除价格，然后在int max中加1，其中max =当前使用的硬币数量 . 然后，递归调用具有price = price-minimum denomination的函数 .

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

我的基本情况是，如果

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 }

我相信我的问题是我扣除了用于定价的硬币数量（而不是硬币的 Value ） . 但我真的不知道如何使用合适的//什么样的数据结构来存储我的硬币及其 Value .

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]

回复于 2024-04-25T07:19:52+08:00

算法 - java中的硬币变化

1 回答

相关问题