C++ implémentation de knapsack branch et bound
j'essaie de mettre en place une implémentation C++ de ce problème knapsack en utilisant branch et bounding. Il y a une version Java sur ce site ici:la mise en Œuvre de branch and bound pour le sac à dos
j'essaie de faire imprimer ma version C++ sur le 90 qu'elle devrait, mais elle ne le fait pas, à la place, elle imprime sur le 5.
est-ce que quelqu'un sait où et quel est le problème?
#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 réponses
je pense que vous avez mis les valeurs du profit et du poids dans les mauvais vecteurs. Modifier:
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};
et votre programme va sortir 90.
je crois que ce que vous mettez en œuvre n'est pas un algorithme de branche et lié exactement. C'est plus comme une estimation basée sur un retour en arrière si je dois l'apparier avec quelque chose.
Le problème dans votre algorithme est la structure de données que vous utilisez. Ce que vous faites est tout simplement de la première pousser tous les premiers niveaux, puis de pousser tous les niveaux, et ensuite de pousser tous les niveaux de la file d'attente et les faire revenir dans leur ordre d'insertion. Vous obtiendrez votre résultat, mais c'est simplement rechercher l'ensemble de l'espace de recherche.
au lieu de poper les éléments avec leur ordre d'insertion, ce que vous devez faire est de se ramifier toujours sur le noeud qui a la limite estimée la plus élevée. En d'autres termes, vous vous ramifiez toujours sur chaque noeud de votre manière, indépendamment de leurs limites estimées. La technique de la branche et liée tire son avantage de vitesse de la ramification sur un seul noeud à chaque fois ce qui est le plus probable pour conduire au résultat (a le plus haut estimé valeur.)
exemple : dans votre première itération, supposez que vous avez trouvé 2 noeuds avec des valeurs estimées
node1: 110
node2: 80
vous les poussez tous les deux à votre file d'attente. Votre file d'attente est devenue "N2-N1-head" dans la deuxième itération vous poussez deux noeuds supplémentaires après branchement sur node1:
nœud3: 100
nœud4: 95
et vous les ajouter à votre file d'attente aussi bien("n4-n3-n2-head". De là vient l'erreur. Dans la prochaine itération ce que vous allez obtenir sera node2 mais à la place, il devrait être node3 qui a la valeur estimée la plus élevée.
donc si Je ne manque rien dans votre code, votre implémentation et l'implémentation java sont fausses. Vous devriez plutôt utiliser une file d'attente prioritaire (heap) pour implémenter une branche réelle et liée.
vous réglez le W à 16, donc le résultat est 5. Le seul article que vous pouvez prendre dans le sac à dos est l'article 3 avec le bénéfice 5 et le poids 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**