不同硬币的硬币变化上限不同吗？

Question

示例输入:2010 25 2

示例输出:2

说明:20 的金额可以通过两种方式获得:10*210*1 + 5*2

我想找出使用​​给定硬币可以制作特定金额的方法数。在示例中，输入 20 是要制作的金额，下一行显示硬币值(value)和该值(value)的硬币数量，即 2值(value) 10 的硬币。输出有用这些硬币制作 20 的方法。我已经尝试了递归解决方案，但无法正常工作。我应该使用什么算法来解决这个问题？

   #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;
}

出于某种原因，我总是得到 0 作为答案。请提供所有帮助。

Answer 1

您的代码存在一些问题:

int compare(const struct pair *elem1 ,const struct pair *elem2)
{
    if ( elem2->coin > elem1->coin && elem2->numberofcoin>0)
        return 1;
    else
        return -1;
}

此比较函数不适合传递给qsort。对于相等的参数，它不会返回 0，并且可能会发生 compare(x,y) == -1 ==compare(y,x) 的情况。因此，qsort 可能会使用该比较函数循环，或产生不正确的结果。但是，根据您获得的数据，这可能不会影响您。

for(i=0;i<nc;i++)
{
    a[i].numberofcoin=amount/a[i].coin;
}

这个循环背后的想法是什么？我无法理解它。删除该循环有助于获得示例测试用例的正确结果，并且更有意义，因为您对该面额的可用硬币感兴趣。

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++;
}

将 a[j].numberofcoin 作为 current 参数传递给递归调用是没有意义的。为什么您只考虑面额小于某些(可能是其他)面额的硬币剩余数量的硬币？事实上，这就是导致递归调用中的测试失败的原因，因此递归永远不会超出示例中的 amount - one_coin。在这里传递a[j].coin对于修剪重复项是有意义的。

printf("%d\n",wa(amount,a,nc,10));

为什么在 main 中将考虑的面额限制为最多 10 个？如果有更大面额的可用，您不会考虑使用它们的任何解决方案。