Рубрики

Реализация ранца 0/1 с использованием Branch and Bound

Настоятельно рекомендуем ссылаться на приведенный ниже пост в качестве предварительного условия для этого.

Ветвь и Связанный | Комплект 1 (Введение с рюкзаком 0/1)

Мы обсудили различные подходы для решения вышеупомянутой проблемы и увидели, что решение «Ветвь и граница» является наиболее подходящим методом, когда веса элементов не являются целыми числами.

В этом посте обсуждается реализация метода Branch and Bound для задачи о ранце 0/1.

Как найти границу для каждого узла для рюкзака 0/1?
Идея состоит в том, чтобы использовать тот факт, что подход Greedy обеспечивает лучшее решение проблемы дробного ранца.
Чтобы проверить, может ли конкретный узел дать нам лучшее решение или нет, мы вычисляем оптимальное решение (через узел), используя подход Greedy. Если решение, рассчитанное самим подходом Greedy, на данный момент является более чем лучшим, то мы не можем получить лучшее решение через узел.

Полный алгоритм:

  1. Сортируйте все элементы в порядке убывания соотношения стоимости на единицу веса, чтобы можно было рассчитать верхнюю границу с использованием жадного подхода.
  2. Инициализировать максимальную прибыль, maxProfit = 0
  3. Создать пустую очередь, Q.
  4. Создайте фиктивный узел дерева решений и поставьте его в очередь Q. Прибыль и вес фиктивного узла равны 0.
  5. Делайте следующее, пока Q не пусто.
    • Извлеките предмет из Q. Пусть извлеченный предмет будет u.
    • Вычислить прибыль узла следующего уровня. Если прибыль превышает maxProfit, обновите maxProfit.
    • Вычислить границу узла следующего уровня. Если граница больше, чем maxProfit, то добавьте узел следующего уровня в Q.
    • Рассмотрим случай, когда узел следующего уровня не рассматривается как часть решения, и добавьте узел в очередь со следующим уровнем, но с весом и прибылью без учета узлов следующего уровня.

Иллюстрация :

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.

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

Ниже приводится реализация вышеуказанной идеи на C ++.

// C ++ программа для решения проблемы с рюкзаком
// ветвь и граница
#include <bits/stdc++.h>

using namespace std;

  
// Структура для Item, который хранит вес и соответствует
// значение Item

struct Item

{

    float weight;

    int value;

};

  
// Структура узла для хранения информации о решении
// дерево

struct Node

{

    // уровень -> уровень узла в дереве решений (или индексе

    // в обр []

    // прибыль -> прибыль узлов на пути от корня к этому

    // узел (включая этот узел)

    // bound ---> Верхняя граница максимальной прибыли в поддереве

    // этого узла /

    int level, profit, bound;

    float weight;

};

  
// Функция сравнения для сортировки Item по
// соотношение вес / вес

bool cmp(Item a, Item b)

{

    double r1 = (double)a.value / a.weight;

    double r2 = (double)b.value / b.weight;

    return r1 > r2;

}

  
// Возвращает границу прибыли в поддереве с корнем u.
// Эта функция в основном использует решение Greedy для поиска
// верхняя граница максимальной прибыли.

int bound(Node u, int n, int W, Item arr[])

{

    // если вес превышает вместимость рюкзака, вернуть

    // 0 как ожидаемая граница

    if (u.weight >= W)

        return 0;

  

    // инициализировать привязку прибыли к текущей прибыли

    int profit_bound = u.profit;

  

    // начинаем включать элементы от индекса 1 до текущего

    // предметный указатель

    int j = u.level + 1;

    int totweight = u.weight;

  

    // проверка состояния индекса и вместимости ранца

    // условие

    while ((j < n) && (totweight + arr[j].weight <= W))

    {

        totweight    += arr[j].weight;

        profit_bound += arr[j].value;

        j++;

    }

  

    // Если k не n, включить последний элемент частично для

    // верхняя граница прибыли

    if (j < n)

        profit_bound += (W - totweight) * arr[j].value /

                                         arr[j].weight;

  

    return profit_bound;

}

  
// Возвращает максимальную прибыль, которую мы можем получить с мощностью W

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);

  

    // один за другим извлекаем элемент из дерева решений

    // вычисляем прибыль всех потомков извлеченного предмета

    // и сохраняем maxProfit

    int maxProfit = 0;

    while (!Q.empty())

    {

        // Отмена очереди узла

        u = Q.front();

        Q.pop();

  

        // Если это начальный узел, назначаем уровень 0

        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;

  

        // Если накопленный вес меньше W и

        // прибыль больше предыдущей прибыли,

        // обновляем maxprofit

        if (v.weight <= W && v.profit > maxProfit)

            maxProfit = v.profit;

  

        // Получить верхнюю границу прибыли, чтобы решить

        // добавлять или нет v в Q или нет.

        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 = 10;   // Вес рюкзака

    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;

}

Выход :

Maximum possible profit = 235

Эта статья предоставлена Уткарш Триведи. Если вам нравится GeeksforGeeks и вы хотели бы внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Рекомендуемые посты:

Реализация ранца 0/1 с использованием Branch and Bound

0.00 (0%) 0 votes