N coins problem with sum equal to S - Dynamic programming
Given a list of N coins, their values (V1, V2, … , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it's not possible to select coins in such a way that they sum up to S.
We will create an array Min[i] for minimal sets with sum = i. Min[0]=0.
We come through i=1 to S inclusive and check whether Min[i]>Min[Min[i-v]+1] for each v in a given array. If so, we set Min[i] to this value.
Read full article from N coins problem with sum equal to S - Dynamic programming
Given a list of N coins, their values (V1, V2, … , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it's not possible to select coins in such a way that they sum up to S.
We will create an array Min[i] for minimal sets with sum = i. Min[0]=0.
We come through i=1 to S inclusive and check whether Min[i]>Min[Min[i-v]+1] for each v in a given array. If so, we set Min[i] to this value.
int minCoins( int a[], int N, int S ){ |
/* N: Length of the array */ |
int *min = (int *)malloc(sizeof(int)*(S+1)); |
int i,j; |
for(i=0;i<=S;i++) |
min[i]= INT_MAX; // start with extremly large value |
min[0]=0; |
for(i=1;i<=S;i++) |
{ |
for(j=0;j<N;j++) |
{ |
if(i>=a[j]) |
{ |
if(min[i-a[j]]+1<min[i]) |
min[i] = min[i-a[j]]+1; |
} |
} |
} |
if(min[S]== INT_MAX) |
return -1; |
return min[S]; |
} |
