Given a value N, we want to make change for N cents and we have infinite supply of each of S={S1, S2...Sm}valued coins, how many ways we can make the change? The order of coins does not matter.
For example for N=4, and S={1,2,3}, there are four solutions: {1,1,1,1}, {1,1,2}, {2,2},{1,3}. So output should be 4.
For example for N=4, and S={1,2,3}, there are four solutions: {1,1,1,1}, {1,1,2}, {2,2},{1,3}. So output should be 4.
This is one of the problem which can be solved by dynamic programming. We will use a temporary table which will be created in bottom-up manner. Here is the function.
ReplyDelete#include
int main()
{
int arr[]={1,2,3};
int m=sizeof(arr)/sizeof(arr[0]);
int n=4;
printf("%d ",count(arr,m,n));
return 0;
}
int count(int S[], int m, int n)
{
int table[n+1],i,j;
memset(table,0,sizeof(table));
table[0]=1;
for(i=0;i<m;i++)
{
for(j=S[i];j<=n;j++)
table[j]+=table[j-S[i]];
}
return table[n];
}