Sample Input: 20 10 2 5 2
Sample Output: 2
Explanation: An amount of 20 could be made in 2 ways: 10*2 10*1 + 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 && elem2->numberofcoin>0)
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("case 1\n");
return 1;}
int i=0;
int small=INT_MAX;
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].numberofcoin);
a[j].numberofcoin++;
}
}
}
return ans;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
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++)
{
a[i].numberofcoin=amount/a[i].coin;
}
//printf("%d\n",ways(amount,coin,numberofcoin,nc,10,amount,0));
printf("%d\n",wa(amount,a,nc,10));
return 0;
}
I am always getting 0 as the answer for some reason.Please all help will be appreciated.
Some problems with your code:
int compare(const struct pair *elem1 ,const struct pair *elem2)
{
if ( elem2->coin > elem1->coin && elem2->numberofcoin>0)
return 1;
else
return -1;
}
This comparison function isn't suitable for being passed to qsort. It doesn't return 0 for equal arguments, and compare(x,y) == -1 == compare(y,x) can happen. Thus qsort could loop with that comparison function, or produce incorrect results. However, with the data you get, that may not bite you.
for(i=0;i<nc;i++)
{
a[i].numberofcoin=amount/a[i].coin;
}
What is the idea behind that loop? I can't make sense of it. Deleting that loop helped getting the correct result for the example test case and makes more sense, since you'd be interested in the available coins of that denomination.
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].numberofcoin);
a[j].numberofcoin++;
}
Passing a[j].numberofcoin as the current parameter to the recursive call doesn't make sense. Why would you only consider coins whose denomination is smaller than the number of coins left of some (possibly other) denomination? As is, that is what makes the test fail in the recursive call, so the recursion never goes beyond amount - one_coin in the example. Passing a[j].coin here would make sense to prune duplicates.
printf("%d\n",wa(amount,a,nc,10));
Why are you limiting the considered denominations to a maximum of 10 in main? If there are larger denominations available, you would not consider any solutions using them.