Solution de sac à dos avec Backtraking en C++

Question

J'ai des problèmes pour essayer de résoudre le problème du sac à dos en utilisant le backtraking.

Par exemple, pour les valeurs suivantes, la fonction Knapsack retourne 14 comme la solution, mais le résultat correct doit être 7.

int n = 3, weights[] = {2, 3, 1}, values[] = {6, 15, 7}; 

int solution = 0, max = 2; 


void Knapsack (int i, int max, int value, int *solution) 
{ 
    int k; 

    for (k = i; k < n; k++) { 
    if (weights[k] <= max) { 
     Knapsack (k, max - weights[k], value + values[k], solution); 

     if (value+ values[k] > *solution) 
     *solution= value + values[k]; 
    } 
    } 
} 

Quel est le problème ici?

Answer 1

#include<iostream> 
#include<vector> 

using namespace std; 

int weights[] = {2, 3, 1}, values[] = {6, 15, 7}; 

int solution = 0, n = 3; 

std::vector<int> vsol; 
std::vector<int> temp; 

bool issol; 


void Knapsack (int i, int max, int value) 
{ 
    for (int k = i; k < n; k++) { 
    if (max > 0) 
    { 
     if (weights[k] <= max) 
     { 
      temp.push_back(k); 
      if (value+ values[k] >= solution) 
      { 
      solution = value + values[k]; 
      issol = true; 
      } 
     } 
     if ((k+1) < n) 
     { 
      Knapsack (k+1, max - weights[k], value + values[k]); 
     } 
     else 
     { 
      if (issol == true) 
      { 
      if (! vsol.empty()) vsol.clear(); 
      std::move(temp.begin(), temp.end(), std::back_inserter(vsol)); 
      temp.clear(); 
      issol = false; 
      } else temp.clear(); 
      return; 
     } 
    } 
    else 
    { 
     if (issol == true) 
     { 
      if (! vsol.empty()) vsol.clear(); 
      std::move(temp.begin(), temp.end(), std::back_inserter(vsol)); 
      temp.clear(); 
      issol = false; 
     } else temp.clear(); 
     return; 
    } 
    } 
} 

int main() 
{ 
    Knapsack(0, 2, 0); 
    cout << "solution: " << solution << endl; 
    for(vector<int>::iterator it = vsol.begin(); it != vsol.end(); it++) 
     cout << *it << " "; 
    return 0; 
} 

Vous devez augmenter k de 1 lorsque vous appelez à nouveau la fonction Knapsack pour déplacer l'index vers l'avant.

Ajout d'un code pour imprimer les emplacements d'index de la solution. Si plus d'une solution existe (c'est-à-dire le même total), n'imprime que les emplacements de la dernière solution.