### 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]