If a computer had to solve the same problem, how would it do it? Let us see below. ‘Denomination’ refers to the list of available currency notes: $1, $5, $10 and $50 in this case - each note is a denomination.
In General
Problem: We are given a set of denominations d1,d2,d3,...,dn in increasing order. (Without loss of generality) we assume also that d1=1 (that is, there is always a $1 note, and that is the first denomination) so that it is always possible to produce all amounts from the given denominations. We are also given an amount of money amt. We must use a minimum number of coins (or currency notes) of the given denominations to produce amt.
Great Info http://www.seeingwithc.org/topic1html.html
2 comments :
http://www.topcoder.com/tc?d1=tutorials&d2=dynProg&module=Static
main()
{
int V[3] = {1, 3, 5};
int min[12] = {5,5,5,5,5,5,5,5,5,5,5,5};
int sum = 11,i,j;
min[0] = 0;
for(i = 1;i<=11;i++)
{
for(j= 0;j<3;j++)
{
if((V[j] <= i) && ((min[i-V[j]] + 1) < min[i]))
{
printf("%d %d %d %d\n", min[i-V[j]],i,j,V[j]);
min[i] = min[i-V[j]] + 1;
}
}
}
printf("Min number of coins for sum %d is %d",sum,min[sum]);
}
Post a Comment