Implementación en C++ de la rama de mochila y encuadernado

Question

Estoy intentando una implementación en C++ de este problema de mochila usando ramas y límites. Hay una versión de Java en este sitio web aquí: Implementing branch and bound for knapsack

que estoy tratando de hacer mi versión de C++ imprimir el 90 que debería, sin embargo es no hacer que, en cambio, está imprimiendo 5.

¿El ¿Alguien sabe dónde y cuál puede ser el problema?

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

Answer 1

Creo que ha puesto los valores de ganancia y peso en los vectores incorrectos. Cambio:

int p[4] = {2, 5, 10, 5}; 
int w[4] = {40, 30, 50, 10}; 

a:

int w[4] = {2, 5, 10, 5}; 
int p[4] = {40, 30, 50, 10}; 

y su programa es la salida 90.

Answer 2

se está ajustando el W a 16, por lo que el resultado es 5. El único elemento que puede tener en la mochila es el elemento 3 con el beneficio 5 y el peso 10.

Answer 3

Creo que lo que está implementando no es un algoritmo de división & exactamente. Es más como un retroceso basado en la estimación si tengo que relacionarlo con algo.

El problema en su algoritmo es la estructura de datos que está utilizando. Lo que está haciendo es simplemente presionar primero todos los primeros niveles, y luego presionar todos los segundos niveles, y luego empujar todos los niveles a la cola y volverlos a colocar en su orden de inserción. Obtendrá su resultado, pero esto es simplemente buscar en todo el espacio de búsqueda.

En lugar de mostrar los elementos con su orden de inserción, lo que debe hacer es bifurcar siempre en el nodo que tenga el límite estimado más alto. En otras palabras, siempre se está ramificando en cada nodo en su camino, independientemente de sus límites estimados. La técnica de límite de rama & obtiene su beneficio de velocidad de bifurcarse en un solo nodo cada vez que es más probable que conduzca al resultado (tiene el valor estimado más alto).

Ejemplo: En su primera iteración suponga que ha encontrado 2 nodos con valores estimados

nodo1: 110

nodo2: 80

Estás a ambos empujando a la cola . Su cola se convirtió en "N2-N1-cabeza" En la segunda iteración usted está empujando dos nodos más después de la ramificación en el nodo 1:

nodo3: 100

node4: 95

y que son también los agrega a la cola ("n4-n3-n2-head"). Aparece el error. En la siguiente iteración, lo que obtendrá será el nodo2, pero en su lugar debería ser el nodo3 que tiene el valor estimado más alto.

Así que si no echo de menos algo en tu bacalao Tanto su implementación como la implementación de Java son incorrectas.Debería utilizar una cola de prioridad (heap) para implementar una rama real & enlazada.

Answer 4

 #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**