Implementazione C++ del ramo dello zaino e rilegata

Question

Sto provando a implementare in C++ questo problema dello zaino usando il ramo e il limite. C'è una versione di Java su questo sito qui: Implementing branch and bound for knapsack

Sto cercando di fare la mia versione C++ stampare il 90 che dovrebbe, tuttavia è non fare che, invece, è in corso la stampa 5.

fa qualcuno sa dove e quale potrebbe essere il 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

Penso che tu abbia messo i valori di profitto e di peso nei vettori sbagliati. 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}; 

e il programma sarà in uscita 90.

Answer 2

si sta impostando l'W a 16, quindi il risultato è 5. L'unico elemento che si può prendere in lo zaino è l'articolo 3 con profitto 5 e peso 10.

Answer 3

Credo che quello che state implementando non sia un algoritmo derivato &. È più come una stima basata sul backtracking se devo abbinarla a qualcosa.

Il problema nell'algoritmo è la struttura dati che si sta utilizzando. Quello che stai facendo è semplicemente premere prima tutti i primi livelli, e poi spingere tutti i secondi livelli, e poi spingere tutti i terzi livelli in coda e riprenderli nel loro ordine di inserimento. Otterrai il tuo risultato, ma questo è semplicemente cercando l'intero spazio di ricerca.

Invece di inserire gli elementi con il loro ordine di inserimento, è necessario diramare sempre il nodo con il limite stimato più elevato. In altre parole, si sta sempre ramificando su ogni nodo sulla propria strada, indipendentemente dai limiti stimati. La derivazione & ha la sua velocità di trarre vantaggio dalla ramificazione su un solo nodo ogni volta che è più probabile che porti al risultato (ha il valore stimato più alto).

Esempio: Nella tua prima iterazione per scontato che hai trovato 2 nodi con valori stimati

nodo1: 110

Node2: 80

Siete entrambi spingendo alla coda . La coda è diventato "n2-n1-head" Nella seconda iterazione si sta spingendo ancora due nodi dopo la ramificazione su node1:

node3: 100

node4: 95

e si sono aggiungendoli anche alla coda ("n4-n3-n2-head".) Arriva l'errore Nella prossima iterazione quello che otterrete sarà node2, ma dovrebbe essere node3 che ha il valore stimato più alto

Quindi se non mi manca qualcosa nel tuo merluzzo Sia la tua implementazione che l'implementazione di java sono sbagliate.È preferibile utilizzare una coda di priorità (heap) per implementare un ramo reale & associato.

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