c++ - 动态规划：硬币变化

Question

我有一个输入：

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

作为输出我需要：

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

Answer 1

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

2
10
2
2 5

10
1
9

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

Answer 2

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

在这里，如果coin[i] < s，则整个循环将中断，而您只需要跳过这个硬币。

PS请用正确的代码格式来打扰自己。