在C++中使用Backtraking的背包解决方案

Question

Im试图通过回溯来解决背包问题。

例如，对于下面的值，背包函数将返回14作为解决方案，但正确的结果应该是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]; 
    } 
    } 
} 

这里有什么问题？

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

当您再次调用Knapsack函数以将索引向前移动时，您需要将k增加1。

添加代码以打印解决方案的索引位置。如果存在多个解决方案（即总数相同），则只会打印出最后解决方案的位置。