The change-making problem, also known as minimum coin change problem, addresses the question of finding the minimum number of coins (of certain denominations) that add up to a given amount of money refer coin change problem. It is a knapsack type problem, and has applications wider than just currency.
It is also the most common variation of the coin change problem, a general case of partition in which, given the available denominations of an infinite set of coins, the objective is to find out the number of possible ways of making a change for a specific amount of money, without considering the order of the coins.
public class CoinChangingProblem {
public static void main(String[] args) {
int[] coins = new int[] {1, 2, 3};
int total = 5;
int[][] dp = new int[coins.length][total+1];
for(int i=0;i<coins.length;i++) {
for(int j=0;j<total+1;j++) {
if(j==0)
dp[i][j]=1;
else if(i==0) {
if (coins[i]<=j)
dp[i][j]=1;
}
else if(coins[i]>j)
dp[i][j]=dp[i-1][j];
else
dp[i][j]=dp[i-1][j] + dp[i][j-coins[i]];
}
}
System.out.println(dp[coins.length-1][total]);
}
}
It is weakly NP-hard, but may be solved optimally in pseudo-polynomial time by dynamic programming.
