Given a list of N coins, their values {a1, a2, ...aN} 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 return -1 if it's not possible to select coins in such a way that they sum upto S.
Explanation for algorithm is given here:
http://www.topcoder.com/tc?d1=tutorials&d2=dynProg&module=Static
#include
ReplyDelete#define INFINITE 999999
int main()
{
const int S = 11; // sum to calculate.
const int N = 3; // number of coins available.
int a[N] = {1,3,5}; // face value of all the coins.
int min[S+1];
for(int i=0;i<12;i++)
min[i] = INFINITE; // we havent yet found a solution for this one.
min[0] = 0; // sum of 0 requires minimum number of 0 coins.
for(int s=1;s<=S;s++) // start from 1 since we have found a solution for sum = 0.
{
for(int n=0;n1+min[s-a[n]])
{
min[s] = min[s-a[n]]+1;
}
}
}
return min[S];
}