1

私は入力として持っています：

  1. テストケースの数
  2. 金額

出力として必要なもの：

  1. 私たちが持っているさまざまなコインの数と各コインの価値。

プログラムは解決策があるかどうかを判断する必要があるため、出力は「はい」または「いいえ」のいずれかである必要があります。

動的計画法を使用してプログラムを作成しましたが、一度に1つのテストケースを入力した場合にのみ機能します。たとえば、一度に200のテストケースを作成すると、出力が常に正しくなるとは限りません。

テストケース間で状態が正しく保存されないという問題があると思います。私の質問は、どうすればこの問題を解決できるでしょうか？私はいくつかのアドバイスを求めているだけです。

これが私のコードです：

#include<iostream>
#include<stdio.h>
#include<string>

#define max_muenzwert 1000

  using namespace std;


  int coin[10];//max. 10 coins
  int d[max_muenzwert][10];//max value of a coin und max. number of coins

  int tabelle(int s,int k)//computes table
  {   
    if(d[s][k]!=-1) return d[s][k];
    d[s][k]=0; 

    for(int i=k;i<=9&&s>=coin[i];i++)
      d[s][k]+=tabelle(s-coin[i],i);


    return d[s][k];
 }

 int main()

 {
    int t;
    for(cin>>t;t>0;t--)//number of testcases

     {        

                int n;   //value we are searching   
           scanf("%d",&n)==1;             
          int n1;              

    cin>>n1;//how many coins

    for (int n2=0; n2<n1; n2++)
    {
        cin>>coin[n2];//value of coins
        }

    memset(d,-1,sizeof(d));//set table to -1

    for(int i=0;i<=9;i++)
    {
             d[0][i]=1;//set only first row to 1 
             }

      if(tabelle(n,0)>0) //if there's a solution
      {
                    cout<<"yes"<<endl;

                    }
      else //no solution
      {
           cout<<"no"<<endl;

      }





      }
      //system("pause");
return 0;
}
4

2 に答える 2

1

ご覧のとおり、可変数のコインがあり、次の行を使用して入力を取得していますcin>>n1;//how many coins。しかし、tabelleメソッドでは常に をループしていますが0 - 9、これは間違っています。のみをループする必要があります0 - n1。このテストケースを試してください:

2
10
2
2 5

10
1
9

2 番目のテスト セットでは、答えは次のようになりますnoが、プログラムはyes、コイン配列の 2 番目の要素で 5 を見つけると言うでしょう。

于 2012-04-10T17:42:27.400 に答える
0 
for(int i=k;i<=9&&s>=coin[i];i++)
  d[s][k]+=tabelle(s-coin[i],i);

ここで、 の場合coin[i] < s、ループ全体が壊れますが、このコインをスキップするだけで済みます。

PS 適切なコードの書式設定に気をつけてください。

于 2012-04-10T16:16:47.803 に答える