Coin Change Problem (Using Dynamic Programming)

    /**
     * 
     * @author Vijay Kumar : email kumar.vijay@gmail.com
     * Distributed under Apache 2.0 License
     * 
     * Programatically solves the Coin Change problem. 
     * The program computes the following
     * 1. All possible solutions 
     * 2. The optimal solution.
     * 
     * References:
     * http://condor.depaul.edu/~rjohnson/algorithm/coins.pdf
     * http://www.algorithmist.com/index.php/Coin_Change
     * 
     */
    public class CoinChangeAlgo
    {

        public static void main(string[] args)
        {
            CoinChangeAlgo ch = new CoinChangeAlgo();

            // target is 15 and change is 1,6,7
            CoinChangeAnswer soln = ch.findAllPossibleCombinations(15, new int[] { 1, 6, 7 });
            soln.printAllPossibleCombos();


            // example 2
            soln = ch.findAllPossibleCombinations(4, new int[] { 1, 2, 3 });
            soln.printAllPossibleCombos();

            // example 3
            soln = ch.findAllPossibleCombinations(15, new int[] { 1, 3, 5, 10 });
            soln.printAllPossibleCombos();


            // optimal solution for target=15
            //soln = ch.findOptimalChange(15, new int[] {1,5,3,10});
            soln = ch.findOptimalChange(4, new int[] { 1, 2, 3 });
            Console.WriteLine(soln.getOptimalChange());
        }

        /**
         * 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);
                }
            }
        }

        /**
         * Find all possible solutions for a target amount given the denominations
         * @param target - The target amount, say 12
         * @param denoms - The denominations which must be in an order and must not contain duplicates
         * @return The Answer object which contains the list of all possible solutions.
         */
        public CoinChangeAnswer findAllPossibleCombinations(int target, int[] denoms)
        {
            CoinChangeAnswer soln = new CoinChangeAnswer(target, denoms);
            string tempSoln = string.Empty;
            findAllCombinationsRecursive(tempSoln, 0, target, soln);
            return soln;
        }

        /**
         * Find the optimal solution for a given target value and the set of denomiations
         * @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.GetLength(0); 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;
        }

    }

public class CoinChangeAnswer {
	/**
	 * The optimal solution for i,j where i is the denomination
	 * and j is the current target value.
	 * The final optimal solution is the number of coins required to 
	 * reach the 'target.  The final solution will be the cell with the highest index
	 * eg:- for a target amount of 12 and denomination of 1,6,10 the highest
	 * index will contain the integer value 2 which corresponds to 2 coins 
	 * required to make a target of 12 (using 6,6).
	 */
	public int[,] OPT = new int[0,0];
	/**
	 * similar to the OPT structure, except that the elements are strings of
	 * change for the i,j optimal solution
	 * eg:- for a target amount of 12 and denomination of 1,6,10 the highest
	 * index will contain the string "6 6". 
	 */
	public string[,] optimalChange = new string[0,0];
	
	/**
	 * List of all possible solutions for the target
	 */
	public List allPossibleChanges = new List();
	
	/**
	 * The target value.
	 */
	private int target;
	
	/**
	 * Copy of the denominations that was used to generate this solution
	 */
	public int[] denoms;
	
	public CoinChangeAnswer(int target,int[] denoms) {
		this.target = target;
		this.denoms = denoms;

		optimalChange = ResizeArray(optimalChange,denoms.Length,target+1);
                OPT = ResizeArray(OPT, denoms.Length, target + 1);
	}

    protected T[,] ResizeArray(T[,] original, int x, int y)
    {
        T[,] newArray = new T[x, y];
        int minX = Math.Min(original.GetLength(0), newArray.GetLength(0));
        int minY = Math.Min(original.GetLength(1), newArray.GetLength(1));

        for (int i = 0; i < minY; ++i)
            Array.Copy(original, i * original.GetLength(0), newArray, i * newArray.GetLength(0), minX);

        return newArray;
    }

	public void printAllPossibleCombos( ) {
		if(allPossibleChanges.Count > 0) {
			Console.WriteLine("All possible change(s) Target=" + target + ", Denominations="+denomstring());
			int i=1;
			foreach (string s in allPossibleChanges) {
				Console.WriteLine(i + ") " + s);
				i++;
			}
			Console.WriteLine();
		} else {
			Console.WriteLine("No change for target="+target+ ", Denominations="+denomstring());
		}
		
	}
	
	public string getOptimalChange() {
		int i = optimalChange.GetLength(0);
		int j = optimalChange.GetLength(1);
		string str = "Optimal solution for Target="+target + ", Denominations="+denomstring() + " is (" + optimalChange[i-1,j-1].Trim() +")";
		return str;
	}
	
	public string denomstring( ) {
		StringBuilder sb = new StringBuilder();
		foreach (int i in denoms) {
			sb.Append(i + " ");
		}
		return sb.ToString();
	}
}