Implementación de 0/1 Mochila usando Branch and Bound – Part 1

Recomendamos encarecidamente consultar la publicación a continuación como requisito previo para esto.

Rama y Atado | Set 1 (Introducción con 0/1 Mochila)

Discutimos diferentes enfoques para resolver el problema anterior y vimos que la solución Branch and Bound es el método más adecuado cuando los pesos de los elementos no son números enteros.

En esta publicación, se analiza la implementación del método Branch and Bound para el problema de la mochila 0/1.

¿Cómo encontrar el límite para cada Node para 0/1 Mochila?
La idea es utilizar el hecho de que el enfoque Greedy proporciona la mejor solución para el problema de la mochila fraccional.
Para verificar si un Node en particular puede darnos una mejor solución o no, calculamos la solución óptima (a través del Node) utilizando el enfoque Greedy. Si la solución calculada por el enfoque de Greedy es más que la mejor hasta ahora, entonces no podemos obtener una mejor solución a través del Node.

Algoritmo completo:

  1. Ordene todos los artículos en orden decreciente de relación de valor por unidad de peso para que se pueda calcular un límite superior utilizando el enfoque codicioso.
  2. Inicializar beneficio máximo, maxProfit = 0
  3. Crea una cola vacía, Q.
  4. Cree un Node ficticio del árbol de decisiones y colóquelo en Q. La ganancia y el peso del Node ficticio son 0.
  5. Haz lo siguiente mientras Q no esté vacío.
    • Extraiga un elemento de Q. Deje que el elemento extraído sea u.
    • Calcule la ganancia del Node del siguiente nivel. Si la ganancia es mayor que maxProfit, actualice maxProfit.
    • Calcular el límite del Node del siguiente nivel. Si el límite es mayor que maxProfit, agregue el siguiente Node de nivel a Q.
    • Considere el caso en el que el Node del siguiente nivel no se considera como parte de la solución y agregue un Node a la cola con el nivel como siguiente, pero pondere y obtenga ganancias sin considerar los Nodes del siguiente nivel.

Ilustración :

Input:
// First thing in every pair is weight of item
// and second thing is value of item
Item arr[] = {{2, 40}, {3.14, 50}, {1.98, 100},
              {5, 95}, {3, 30}};
Knapsack Capacity W = 10

Output:
The maximum possible profit = 235

Below diagram shows illustration. Items are 
considered sorted by value/weight.

branchandbound

Note :  The image doesn't strictly follow the 
algorithm/code as there is no dummy node in the
image.

A continuación se muestra la implementación en C++ de la idea anterior.

// C++ program to solve knapsack problem using
// branch and bound
#include <bits/stdc++.h>
using namespace std;
  
// Structure for Item which store weight and corresponding
// value of Item
struct Item
{
    float weight;
    int value;
};
  
// Node structure to store information of decision
// tree
struct Node
{
    // level  --> Level of node in decision tree (or index
    //             in arr[]
    // profit --> Profit of nodes on path from root to this
    //            node (including this node)
    // bound ---> Upper bound of maximum profit in subtree
    //            of this node/
    int level, profit, bound;
    float weight;
};
  
// Comparison function to sort Item according to
// val/weight ratio
bool cmp(Item a, Item b)
{
    double r1 = (double)a.value / a.weight;
    double r2 = (double)b.value / b.weight;
    return r1 > r2;
}
  
// Returns bound of profit in subtree rooted with u.
// This function mainly uses Greedy solution to find
// an upper bound on maximum profit.
int bound(Node u, int n, int W, Item arr[])
{
    // if weight overcomes the knapsack capacity, return
    // 0 as expected bound
    if (u.weight >= W)
        return 0;
  
    // initialize bound on profit by current profit
    int profit_bound = u.profit;
  
    // start including items from index 1 more to current
    // item index
    int j = u.level + 1;
    int totweight = u.weight;
  
    // checking index condition and knapsack capacity
    // condition
    while ((j < n) && (totweight + arr[j].weight <= W))
    {
        totweight    += arr[j].weight;
        profit_bound += arr[j].value;
        j++;
    }
  
    // If k is not n, include last item partially for
    // upper bound on profit
    if (j < n)
        profit_bound += (W - totweight) * arr[j].value /
                                         arr[j].weight;
  
    return profit_bound;
}
  
// Returns maximum profit we can get with capacity W
int knapsack(int W, Item arr[], int n)
{
    // sorting Item on basis of value per unit
    // weight.
    sort(arr, arr + n, cmp);
  
    // make a queue for traversing the node
    queue<Node> Q;
    Node u, v;
  
    // dummy node at starting
    u.level = -1;
    u.profit = u.weight = 0;
    Q.push(u);
  
    // One by one extract an item from decision tree
    // compute profit of all children of extracted item
    // and keep saving maxProfit
    int maxProfit = 0;
    while (!Q.empty())
    {
        // Dequeue a node
        u = Q.front();
        Q.pop();
  
        // If it is starting node, assign level 0
        if (u.level == -1)
            v.level = 0;
  
        // If there is nothing on next level
        if (u.level == n-1)
            continue;
  
        // Else if not last node, then increment level,
        // and compute profit of children nodes.
        v.level = u.level + 1;
  
        // Taking current level's item add current
        // level's weight and value to node u's
        // weight and value
        v.weight = u.weight + arr[v.level].weight;
        v.profit = u.profit + arr[v.level].value;
  
        // If cumulated weight is less than W and
        // profit is greater than previous profit,
        // update maxprofit
        if (v.weight <= W && v.profit > maxProfit)
            maxProfit = v.profit;
  
        // Get the upper bound on profit to decide
        // whether to add v to Q or not.
        v.bound = bound(v, n, W, arr);
  
        // If bound value is greater than profit,
        // then only push into queue for further
        // consideration
        if (v.bound > maxProfit)
            Q.push(v);
  
        // Do the same thing,  but Without taking
        // the item in knapsack
        v.weight = u.weight;
        v.profit = u.profit;
        v.bound = bound(v, n, W, arr);
        if (v.bound > maxProfit)
            Q.push(v);
    }
  
    return maxProfit;
}
  
// driver program to test above function
int main()
{
    int W = 10;   // Weight of knapsack
    Item arr[] = {{2, 40}, {3.14, 50}, {1.98, 100},
                  {5, 95}, {3, 30}};
    int n = sizeof(arr) / sizeof(arr[0]);
  
    cout << "Maximum possible profit = "
         << knapsack(W, arr, n);
  
    return 0;
}

Producción :

Maximum possible profit = 235

Este artículo es una contribución de Utkarsh Trivedi. Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *