Coin Change Problem (Using Dynamic Programming)

• Download source - 7.47 KB

Introduction

Coin change is the problem of finding the number of ways to make change for a target amount given a set of denominations.  It is assumed that there is an unlimited supply of coins for each denomination.  An example will be finding change for target amount 4 using change of 1,2,3 for which the solutions are (1,1,1,1), (2,2), (1,1,2), (1,3).  As you can see, the optimal solution can be (2,2) or (1,3).  The attached Java program solves both the problems of "find all combinations" and "find the optimal solution (which takes the least number of coins)".

Background

Familiarity with Dynamic Programming will help in understanding the solution much more easily.  Read through the following articles to get an algorithmic view of the problem:

• Coin Changing Revisited
• Coin Change

The CoinChangeAnswer Class

An instance of the CoinChangeAnswer stores the result of both the FindAll and FindOptimal problems. The class is just a convenient way to store the results in one place.

 public class CoinChangeAnswer {
	public int OPT[][];  	// contains the optimal solution
				// during every recurrence step.
	public String optimalChange[][]; // string representation of optimal solutions.

	/**
	 * List of all possible solutions for the target
	 */
	public ArrayList<String> allPossibleChanges = new ArrayList<String>();

	/**
	 * The target amount.
	 */
	private int target;

	/**
	 * Copy of the denominations that was used to generate this solution
	 */
	public int[] denoms;
};

All Possible Solutions

Let's first try and solve all the possible ways to make the change for the target amount of 4 using denominations 1, 2, 3.  As you can see, the target amount of 4 can be reached in 4 different ways which are (1,1,1,1), (1,1,2), (1,3), (2,2). Let's try to reach the first answer of (1,1,1,1). If we pick coin '1' then we are left with the target amount of '3', which is a sub problem of the original problem of '4'. We can see solving the sub-problem successively using denomination of '1' leads to '4'. To get to the second solution, we need to deviate and pick '2' after picking (1,1).  How can we know this?  The only way to achieve this is to exhaustively place all denominations in all possible slots until the target amount is reached.  This can be solved by constructing recursive solution to the sub problems.

 /**
   * Find all possible solutions recursively
   * @param tsoln - The current solution string
   * @param startIx - The start index in the denomination array.
   * @param remainingTarget - The remaining target amount to be satisfied.
   * @param answer - The final answer object.
   */
  private void findAllCombinationsRecursive(String tsoln,
          int startIx,
          int remainingTarget,
        CoinChangeAnswer answer) {
    for(int i=startIx; i<answer.denoms.length ;i++) {
        int temp = remainingTarget - answer.denoms[i];
        String tempSoln = tsoln + "" + answer.denoms[i]+ ",";
        if(temp < 0) {
         break;
        }
        if(temp == 0) {
         // reached the answer hence quit from the loop
         answer.allPossibleChanges.add(tempSoln);
         break;
        } 
        else {
        // target not reached, try the solution recursively with the
        // current denomination as the start point.
         findAllCombinationsRecursive(tempSoln, i, temp, answer);
        }
     }
 }

public CoinChangeAnswer findAllPossibleCombinations(int target, int[] denoms) {
	CoinChangeAnswer soln = new CoinChangeAnswer(target,denoms);
	String tempSoln = new String();
	findAllCombinationsRecursive(tempSoln, 0, target, soln);
	return soln;
}

The function findAllCombinationsRecursive is initially called with  the following parameters ("",0,4,finalAnswer). The finalAnswer object is a data structure which will contain the denominations to be used and the list of final solutions. The for loop starts from 'startIx' and runs till the end of denominations and reduces the target amount by the value of the current denomination chosen. If the target reaches zero, then we have a solution which is added to the answer list. If the target is > 0, then we have to create a subproblem with target = target - denoms[i] and the denoms[i] is added to the temporary solution. The function is then called recursively with startIx set to 'i' which means the denoms[i] will be reconsidered in the recursive call. The complexity of the algorithm is O(n^2*T) where n is the number of denominations and T is the target amount.

Optimal Solution 

The optimal solution to this program can be found by using dynamic programming and its runtime can be considerably reduced by a technique called memoization. This document describes an algorithm, which I have translated into the Java function findOptimalChange.   

  /**
   * Find the optimal solution for a given target value and the set of denominations
   * @param target
   * @param denoms
   * @return
   */
  public CoinChangeAnswer findOptimalChange(int target, int[] denoms) {
     CoinChangeAnswer soln = new CoinChangeAnswer(target,denoms);
     StringBuilder sb = new StringBuilder();
       
     // initialize the solution structure
     for(int i=0; i<soln.OPT[0].length ; i++) {
         soln.OPT[0][i] = i;
         soln.optimalChange[0][i] = sb.toString();
         sb.append(denoms[0]+" ");
     }

     // Read through the following for more details on the explanation
     // of the algorithm.
     // http://condor.depaul.edu/~rjohnson/algorithm/coins.pdf
     for(int i=1 ; i<denoms.length ; i++) {
         for(int j=0; j<target+1 ; j++) {
          int value = j;
          int targetWithPrevDenomiation = soln.OPT[i-1][j];
          int ix = (value) - denoms[i];
          if( ix>=0 && (denoms[i] <= value )) {
              int x2 = denoms[i] + soln.OPT[i][ix];
              if(x2 <= target && (1+soln.OPT[i][ix] < targetWithPrevDenomiation)) {
               String temp = soln.optimalChange[i][ix] + denoms[i] + " ";
               soln.optimalChange[i][j] = temp;
               soln.OPT[i][j] = 1 + soln.OPT[i][ix];
              } else {
               soln.optimalChange[i][j] = soln.optimalChange[i-1][j]+ " ";
               soln.OPT[i][j] = targetWithPrevDenomiation;
              }
          } else {
              soln.optimalChange[i][j] = soln.optimalChange[i-1][j];
              soln.OPT[i][j] = targetWithPrevDenomiation;
          }
        }
     }
     return soln;
  }	 

History 

•   28^th January, 2009: Initial post