algorithm - Coin change in java

Question

I have seen quite many coin change problems and this one is quite unique. I tried using DP and recursion but I wasn't able to solve it.

This is the problem:

Let's say given a price, X, where X is in cents and I have 5 finite coin denominations, 1,5,10,20,50. I have different number of 1,5,10,20,50-cent coins. I want to make price X with the maximum number of coins. How do I do it?(Assuming X can always be made with the coins at hand)

For example, if price X = 52 and

i have 3 of 1-cent coins

I have 4 of 5-cent coins

I have 8 of 10-cent coins

I have 6 of 20-cent coins

I have 4 of 50-cent coins

I want to find the maximum number of coins and number of ways that can be used to make this price, in this case: two 1-cent, four 5-cent, 3 10-cent coins will be the answer.

I have thought of a usable algorithm where first, I put the number and value of each coin into an arraylist, then I pass the array list into a recursive function that will:

First, deduct the price with the smallest denomination, then add 1 to int max, where max = number of coins currently used. Then, recursively call the function with price=price-smallest denomination.

Second, I'll recursively call the function by taking the next smallest available denomination.

My base cases are that if

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

EDIT: to add in code.

I modified the question a little bit.

  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 }

I believe my problem is that I was deducting the number of coins(instead of the value of coin) used to make the price. But I really have no idea how to use a suitable//what kind of data structure to store my coins and its value.

Answer 1

You can use a list to keep track of which coins have been added at each point in the recursion. Use a 2nd list to keep track of the current maximum solution. When you find a solution check if it has more coins than the current max.

Here's some Java code to illustrate:

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]++;
        }
    }
}

Output:

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