count number of coins
Given a list of 3 coins, their values (1,3,5), and the total sum 11. Find the minimum number of coins the sum of which is 11 (we can use as many coins of one type as we want).
Hint: use dynamic programming
Hint: use dynamic programming
int count_coins(int * coin,int len,int money)
ReplyDelete{
int arr[100];
for(int i=0;i<100;i++)
{
arr[i]=999;
}
arr[0]=0;
for(int i=0;i<=money;i++)
{
for(int j=0;j=0)
{
arr[i]=min(arr[i],1+arr[i-coin[j]]);
}
}
}
return arr[money];
}
typo error for 2nd loop: for(int j=0;j<len;j++)
ReplyDelete@ankit why initially you have taken array of 100 elements...
ReplyDelete@priyaranjan ... ummmm lazyness i dint want to write
ReplyDeleteint * arr=(int *)malloc(money*sizeof(int));
;)
so i assumed that maximum money that user wud input is 99
Btw..is the code correct?
Hi
DeleteTry for S=3. array[5,2,1]
answer shd be 2, it gives 1.
I think before
arr[i]=min(arr[i],1+arr[i-coin[j]]);
you shd add
if(i>=coin[j])
that wud do!
@anonymous please see the below comment, it depicts the same logic..:)
Delete@ankit yeah rest logic is correct..:)
ReplyDeleteSet Min[i] equal to Infinity for all of i
ReplyDeleteMin[0]=0
For i = 1 to S
For j = 0 to N - 1
If (Vj<=i AND Min[i-Vj]+1<Min[i])
Then Min[i]=Min[i-Vj]+1
Output Min[S]