backtracking — решение для ранцев с возвратом в стеке
У меня проблемы с попыткой решить проблему ранца с помощью возврата.
Например, для следующих значений функция Knapsack вернет 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];
}
}
}
В чем здесь проблема?
Решение
#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;
}
Вам нужно увеличить k на 1, когда вы снова вызываете функцию ранца, чтобы переместить индекс вперед.
Добавлен код для распечатки индексных мест решения. Если существует более одного решения (т. Е. Общее количество), будут распечатаны только местоположения для последнего решения.
Другие решения