-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 に答える