programme de sac à dos, temps de fonctionnement lent

Question

J'ai modifié du code d'Internet pour répondre à mes exigences, mais malheureusement, ce programme semble courir un peu lent. je ne sais pas si c'est mon ordinateur ou le programme lui-même est lent.

int max(int a, int b) 
{ 
    return (a > b) ? a : b; 
} 

int knapSack(int W, int wt[], int val[], int n) 
{ 

    if (n == 0 || W == 0) 
     return 0; 


    if (wt[n - 1] > W) 
     return knapSack(W, wt, val, n - 1); 

    else 
     return max(val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1), 
       knapSack(W, wt, val, n - 1)); 
} 


int main() 
{ 
     char exeAgain='n'; 

     do 
     { 

     cout << "Enter the number of items in a Knapsack : "; 
     int n, W; 
     cin >> n; 
     int val[n], wt[n]; 
     for (int i = 0; i < n; i++) 
     { 
      val[i]=(rand()%100)+1; 
      wt[i]=(rand()%100)+1; 
      cout << "Item Number "<< i+1 << " value "<<val[i]<<" weight " << wt[i] << endl; 

     } 


     cout << "Enter the capacity of knapsack : "; 
     cin >> W; 
     cout << "The total profit is " << knapSack(W, wt, val, n)<< endl; 

     cout<<"Would you like to execute this program again? [Y/N] : "; 
     cin>>exeAgain; 
     } 
     while(exeAgain == 'y' || exeAgain == 'Y'); 

    return 0; 
} 

Est-il normal que ce programme s'exécute lentement? (l'entrée est 200 & 1500) plus petite entrée est rapide, mais quand j'utilise grand nombre, le programme ralentit.

Answer 1

Le Knapsack Problem est célèbre NP-Complete, ce qui signifie en termes simples que plus la taille de votre entrée augmente, plus le temps de résolution augmente astronomiquement. Alors oui, il est tout à fait normal que votre programme fonctionne lentement avec des entrées plus grandes. Si vous faites des recherches, vous trouverez beaucoup de travail sur le problème, y compris diverses stratégies pour courir plus vite qu'une première tentative, ou des heuristiques pour une solution bonne mais pas parfaite, qui fonctionnera plus vite que quelque chose à la recherche d'une solution parfaite.