-1

样本输入：20 10 2 5 2

样本输出：2

说明：20的数量可以通过2种方式制作：10*2 10*1 + 5*2

我想找出用给定硬币制作特定数量的方法的数量。在示例输入中，20 是要制作的数量，下一行显示硬币价值和该价值的硬币数量，即 2 个有价值的硬币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 作为答案。请提供所有帮助。

4

1 回答 1

2

您的代码存在一些问题：

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));

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

于 2012-07-12T12:57:53.473 回答