Gibt es eine Lösung anstelle von Rucksack Rucksackrückverfolgung Algorithmus in C++

Question

Ich habe die Lösung der Backtracking von Knapsack-Lösung mit C++. Ich hatte die Lösung von hier wieder. Knapsack solution with Backtraking in c++ Mein Compiler gibt Fehler bei der Zeilenverschiebung. Gibt es eine Lösung ohne Verwendung von move? Wie kann ich den Code ändern, ohne den Umzug zu benutzen?

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

Answer 1

können Sie std::move mit std::copy ändern. Im Allgemeinen sind sie nicht äquivalent, aber hier arbeiten Sie mit einem Vektor von int (es gibt also keine Leistungseinbußen) und das Quell-Array wird sofort gelöscht (temp.clear()).

So können Sie schreiben:

if (!vsol.empty()) vsol.clear(); 
std::copy(temp.begin(), temp.end(), std::back_inserter(vsol)); 

der Tat das ist über gedacht. Die einfach:

vsol = temp; 

klar, schnell und arbeitet mit 98 ++ C auch (abhängig von Ihrer C++ Builder-Version, C++ 11-Kompatibilität könnte ein Problem sein).

Die modifizierte Version:

#include <iostream> 
#include <vector> 

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) 
     { 
      vsol = temp; 
      issol = false; 
     } 

     temp.clear(); 
     return; 
     } 
    } 
    else 
    { 
     if (issol) 
     { 
     vsol = temp; 
     issol = false; 
     } 

     temp.clear(); 
     return; 
    } 
    } 
} 

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

    return 0; 
}