Question: Write the code for a change vending machine.

Solution: Use Dynamic Programming
/**
* 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][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 for(int j=0; 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;
}