динамическое программирование: изменение монеты

Question

У меня в качестве входного сигнала:

1. количество testcases
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

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

Здесь, если coin[i] < s, то весь цикл будет ломаться, в то время как вам нужно только, чтобы пропустить эту монету.

P.S. Пожалуйста, позаботьтесь о правильном форматировании кода.

Answer 2

Как вы можете видеть, у вас есть переменное количество монет, которые вы принимаете с использованием этой строки: cin>>n1;//how many coins. Но в методе tabelle вы всегда перебираете 0 - 9, что неверно. Вы должны пройти только через 0 - n1. Попробуйте этот тестовый случай:

 
2 
10 
2 
2 5 

10 
1 
9 

Для второго теста установить ваш ответ должен быть no, но ваша программа будет говорить yes, как это будет найти 5 во втором элементе вашего массива монет.