Sample Input: 20 10 2 5 2
Sample Output: 2
Explanation: An amount of 20 could be made in 2 ways: 102 101 + 5*2
I want to find out the number of ways a particular amount can be made with given coins.In the sample input 20 is the amount to be made and the next line shows the coin value and number of coins of that value ie 2 coins of value 10.Output has the number of ways 20 can be made with these coins.I have tried out a recursive solution but is not working properly.What algorithm should I use to solve this problem?
#include<stdlib.h>
#include<limits.h>
#include<stdio.h>
typedef int (*compfn)(const void*, const void*);
struct pair
{
int coin;
int numberofcoin;
};
int compare(const struct pair *elem1 ,const struct pair *elem2)
{
if ( elem2->coin > elem1->coin )
return 1;
else
return -1;
}
void print(struct pair a[],int ncoin)
{
int i=0;
putchar('\n');
for(i=0;i<ncoin;i++)
{
printf("%d\t%d\n",a[i].coin,a[i].numberofcoin);
}
putchar('\n');
}
int wa(int n,struct pair a[],int numberofdenominations,int current)
{print(a,numberofdenominations);
printf("the amount here %d\n",n);
int ans=0;
if(n==0)
{ puts("final\n"); print(a,numberofdenominations); puts("case 1\n");
return 1;
}
int i=0;
int small=INT_MAX;
if(n<0)
return 0;
for(i=0;i<numberofdenominations;i++)
{
if(small>a[i].coin&&a[i].numberofcoin)
{
small=a[i].coin;
}
}
if(n<small||n<0)
{
puts("case 2\n");
return 0;
}
else
{
puts("case 3\n");
//print(a,numberofdenominations);
qsort(a, numberofdenominations, sizeof(a), (compfn)compare);
puts("after sort\n");
// print(a,numberofdenominations);
int j=0;
for(j=0;j<numberofdenominations;j++)
{
if(a[j].numberofcoin>0&&a[j].coin<=current)
{
puts("case if\n");
a[j].numberofcoin--;
ans+=wa(n-a[j].coin,a,numberofdenominations,a[j].coin);
a[j].numberofcoin++;
}
}
}
return ans;
}
int main()
{
int nc=0;
scanf("%d",&nc);
int amount=0;
int coin[50];
int numberofcoin[50];
struct pair a[51];
int i=0;
for(i=0;i<nc;i++)
{
//scanf("%d%d",&c[i],&numberofcoin[i]);
scanf("%d%d",&a[i].coin,&a[i].numberofcoin);
}
scanf("%d",&amount);
for(i=0;i<nc;i++)
{
//if(amount>a[i].coin*a[i].numberofcoin)
// a[i].numberofcoin=amount/a[i].coin;
}
//qsort(a, nc, sizeof(a), (compfn)compare);
printf("%d\n",wa(amount,a,nc,10));
return 0;
}