c++ - 动态规划 : coin change

Question

我有一个输入:

1. 测试用例数量
2. 一笔钱

作为我需要的输出:

1. 我们拥有的不同硬币的数量以及每枚硬币的值(value)。

程序应该确定是否有解决方案，因此输出应该是"is"或“否”。

我使用动态规划编写了程序，但它仅在我一次输入一个测试用例时有效如果我一次编写比方说 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;
}

Answer 1

如您所见，您拥有可变数量的硬币，您正在使用以下行输入:cin>>n1;//how many coins。但是在 tabelle 方法中，您总是在 0 - 9 中循环，这是错误的。您应该只循环遍历 0 - n1。试试这个测试用例:

21022 51019

对于第二个测试集，你的答案应该是no，但你的程序会说yes，因为它会在硬币数组的第二个元素中找到 5。