алгоритм - Размен монет в 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 центу, четыре монеты по 5 центов, 3 монеты по 10 центов.

Я придумал полезный алгоритм, в котором сначала я помещаю количество и стоимость каждой монеты в список массивов, а затем передаю список массивов в рекурсивную функцию, которая будет:

Сначала вычтите цену с наименьшим номиналом, затем добавьте 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 }

Я считаю, что моя проблема в том, что я вычитал количество монет (вместо стоимости монеты), использованных для определения цены. Но я действительно понятия не имею, как использовать подходящую //какую структуру данных для хранения моих монет и их стоимости.