title: algorithm - Coin change in java
body: <p>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. </p>
  
  <p>This is the problem:</p>
  
  <p>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)</p>
  
  <p>For example, if price X = 52 and</p>
  
  <p>i have 3 of 1-cent coins</p>
  
  <p>I have 4 of 5-cent coins</p>
  
  <p>I have 8 of 10-cent coins</p>
  
  <p>I have 6 of 20-cent coins</p>
  
  <p>I have 4 of 50-cent coins</p>
  
  <p>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. </p>
  
  <p>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:</p>
  
  <p>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.</p>
  
  <p>Second, I'll recursively call the function by taking the next smallest available denomination. </p>
  
  <p>My base cases are that if</p>
  
  <pre><code>1) price &lt;0, return 0
  
  2) if price ==0 and max=currMax,  return 1
  
  3) if price&gt;0, recursively call the 2 recursions listed above
  </code></pre>
  
  <p>EDIT: to add in code.</p>
  
  <p>I modified the question a little bit. </p>
  
  <pre><code>  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&lt;Integer&gt; coins = new ArrayList&lt;Integer&gt;(); //kinds of coins. assumed to be 1,5,10,20,50
    9         for (int i = 0; i &lt;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&lt;Integer&gt; coins,int currMax){
   18         currMax += 1;
   19         if (coins.size()==0) return;             
                else if((coins.get(0)&lt;0)||(price&lt;0)){
   20             //check if AL is empty(no way to make change), smallest coin &lt; 0(invalid), price&lt;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&gt;max){
   28                 way = 1;
   29                 max = currMax;
   30             }
   31         }
   32         else if(price&gt;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 }
  </code></pre>
  
  <p>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.</p>