C++ реализация ранцевых ветвей и границ
Я пытаюсь в C++ реализовать эту проблему ранца с помощью ветвления и ограничения. Здесь есть версия Java на этом сайте: Реализация веток и связок для ранца
Я пытаюсь сделать так, чтобы моя версия на C++ распечатала 90-й, который должен был быть, но он этого не делает, вместо этого он печатает 5.
Кто-нибудь знает где и в чем может быть проблема?
#include <queue>
#include <iostream>
using namespace std;
struct node
{
int level;
int profit;
int weight;
int bound;
};
int bound(node u, int n, int W, vector<int> pVa, vector<int> wVa)
{
int j = 0, k = 0;
int totweight = 0;
int result = 0;
if (u.weight >= W)
{
return 0;
}
else
{
result = u.profit;
j = u.level + 1;
totweight = u.weight;
while ((j < n) && (totweight + wVa[j] <= W))
{
totweight = totweight + wVa[j];
result = result + pVa[j];
j++;
}
k = j;
if (k < n)
{
result = result + (W - totweight) * pVa[k]/wVa[k];
}
return result;
}
}
int knapsack(int n, int p[], int w[], int W)
{
queue<node> Q;
node u, v;
vector<int> pV;
vector<int> wV;
Q.empty();
for (int i = 0; i < n; i++)
{
pV.push_back(p[i]);
wV.push_back(w[i]);
}
v.level = -1;
v.profit = 0;
v.weight = 0;
int maxProfit = 0;
//v.bound = bound(v, n, W, pV, wV);
Q.push(v);
while (!Q.empty())
{
v = Q.front();
Q.pop();
if (v.level == -1)
{
u.level = 0;
}
else if (v.level != (n - 1))
{
u.level = v.level + 1;
}
u.weight = v.weight + w[u.level];
u.profit = v.profit + p[u.level];
u.bound = bound(u, n, W, pV, wV);
if (u.weight <= W && u.profit > maxProfit)
{
maxProfit = u.profit;
}
if (u.bound > maxProfit)
{
Q.push(u);
}
u.weight = v.weight;
u.profit = v.profit;
u.bound = bound(u, n, W, pV, wV);
if (u.bound > maxProfit)
{
Q.push(u);
}
}
return maxProfit;
}
int main()
{
int maxProfit;
int n = 4;
int W = 16;
int p[4] = {2, 5, 10, 5};
int w[4] = {40, 30, 50, 10};
cout << knapsack(n, p, w, W) << endl;
system("PAUSE");
}
4 ответа
Я думаю, что вы поместили значения прибыли и веса в неправильные векторы. Изменить:
int p[4] = {2, 5, 10, 5};
int w[4] = {40, 30, 50, 10};
чтобы:
int w[4] = {2, 5, 10, 5};
int p[4] = {40, 30, 50, 10};
и ваша программа выведет 90.
Я считаю, что то, что вы реализуете, не является алгоритмом ветвления и ограничения. Это больше похоже на откат, основанный на оценке, если мне нужно что-то сопоставить.
Проблема в вашем алгоритме - это структура данных, которую вы используете. Что вы делаете, это просто сначала нажмите все первые уровни, а затем нажмите все вторые уровни, а затем подтолкнуть все третьи уровни в очередь и вернуть их в порядке их вставки. Вы получите свой результат, но это просто поиск по всему пространству поиска.
Вместо того, чтобы извлекать элементы с их порядком вставки, вам нужно всегда выполнять ветвление на узле с наивысшей оценочной границей. Другими словами, вы всегда разветвляетесь на каждом узле на своем пути независимо от их предполагаемых границ. Техника ветвления и привязки получает преимущество в скорости от ветвления только на одном узле каждый раз, что наиболее вероятно приведет к результату (имеет наибольшее оценочное значение).
Пример: в вашей первой итерации предположим, что вы нашли 2 узла с оценочными значениями
узел1: 110
узел2: 80
Вы толкаете их обоих в свою очередь. Ваша очередь стала "n2-n1-head" Во второй итерации вы добавляете еще два узла после ветвления на node1:
узел 3: 100
узел4: 95
и вы также добавляете их в свою очередь ("n4-n3-n2-head". Возникает ошибка. В следующей итерации вы получите узел 2, но вместо него должен быть узел 3 с наивысшей оценкой). значение.
Так что если я не пропущу что-то в вашем коде, то и ваша реализация, и реализация java неверны Вы должны использовать приоритетную очередь (кучу) для реализации реальной ветки и привязки.
Вы устанавливаете W на 16, поэтому результат равен 5. Единственный предмет, который вы можете взять в рюкзак, это предмет 3 с прибылью 5 и весом 10.
#include <bits/stdc++.h>
using namespace std;
struct Item
{
float weight;
int value;
};
struct Node
{
int level, profit, bound;
float weight;
};
bool cmp(Item a, Item b)
{
double r1 = (double)a.value / a.weight;
double r2 = (double)b.value / b.weight;
return r1 > r2;
}
int bound(Node u, int n, int W, Item arr[])
{
if (u.weight >= W)
return 0;
int profit_bound = u.profit;
int j = u.level + 1;
int totweight = u.weight;
while ((j < n) && (totweight + arr[j].weight <= W))
{
totweight = totweight + arr[j].weight;
profit_bound = profit_bound + arr[j].value;
j++;
}
if (j < n)
profit_bound = profit_bound + (W - totweight) * arr[j].value /
arr[j].weight;
return profit_bound;
}
int knapsack(int W, Item arr[], int n)
{
sort(arr, arr + n, cmp);
queue<Node> Q;
Node u, v;
u.level = -1;
u.profit = u.weight = 0;
Q.push(u);
int maxProfit = 0;
while (!Q.empty())
{
u = Q.front();
Q.pop();
if (u.level == -1)
v.level = 0;
if (u.level == n-1)
continue;
v.level = u.level + 1;
v.weight = u.weight + arr[v.level].weight;
v.profit = u.profit + arr[v.level].value;
if (v.weight <= W && v.profit > maxProfit)
maxProfit = v.profit;
v.bound = bound(v, n, W, arr);
if (v.bound > maxProfit)
Q.push(v);
v.weight = u.weight;
v.profit = u.profit;
v.bound = bound(v, n, W, arr);
if (v.bound > maxProfit)
Q.push(v);
}
return maxProfit;
}
int main()
{
int W = 55; // Weight of knapsack
Item arr[] = {{10, 60}, {20, 100}, {30, 120}};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum possible profit = "
<< knapsack(W, arr, n);
return 0;
}
**SEE IF THIS HELPS**