Рубрики

Проблема упаковки бункера (свести к минимуму количество используемых бинов)

Учитывая n элементов разного веса и бункеров, каждый из которых имеет емкость c, назначьте каждый элемент бункеру таким образом, чтобы общее количество использованных бункеров было минимальным. Можно предположить, что все предметы имеют вес меньше вместимости бункера.

Пример:

Input:  wieght[]       = {4, 8, 1, 4, 2, 1}
        Bin Capacity c = 10
Output: 2
We need minimum 2 bins to accommodate all items
First bin contains {4, 4, 2} and second bin {8, 2}

Input:  wieght[]       = {9, 8, 2, 2, 5, 4}
        Bin Capacity c = 10
Output: 4
We need minimum 4 bins to accommodate all items.  

Input:  wieght[]       = {2, 5, 4, 7, 1, 3, 8}; 
        Bin Capacity c = 10
Output: 3

Нижняя граница
Мы всегда можем найти нижнюю границу минимального необходимого количества бинов. Нижняя граница может быть задана как:

   Min no. of bins  >=  Ceil ((Total Weight) / (Bin Capacity))
  

В приведенных выше примерах нижняя граница для первого примера — «ceil (4 + 8 + 1 + 4 + 2 + 1) / 10» = 2, а нижняя граница во втором примере — «ceil (9 + 8 + 2 + 2 + 5»). + 4) / 10 ”= 3.
Эта проблема представляет собой сложную задачу NP, и нахождение точного минимального количества бинов занимает экспоненциальное время. Ниже приведены приблизительные алгоритмы для этой проблемы.

Приложения

  1. Погрузка контейнеров типа грузовиков.
  2. Размещение данных на нескольких дисках.
  3. Планирование работы.
  4. Упаковка рекламы в перерывы на радиостанции фиксированной длины.
  5. Хранение большой коллекции музыки на кассетах / компакт-дисках и т. Д.

Интернет алгоритмы
Эти алгоритмы предназначены для задач, связанных с упаковкой в бункеры, когда элементы поступают по одному (в неизвестном порядке), каждый из которых должен быть помещен в корзину перед рассмотрением следующего элемента.

1. Следующая посадка:
При обработке следующего элемента убедитесь, что он помещается в тот же лоток, что и последний элемент. Используйте новую корзину, только если это не так.

Ниже приведена реализация C ++ для этого алгоритма.

C ++

// C ++ программа для поиска необходимого количества бинов
// следующий алгоритм подбора.
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает количество бинов, необходимое при следующей подгонке
// онлайн алгоритм

int nextFit(int weight[], int n, int c)

{

    // Инициализируем результат (Количество бинов) и оставшиеся

    // емкость в текущей корзине

    int res = 0, bin_rem = c;

  

    // Размещаем предметы по одному

    for (int i = 0; i < n; i++) {

        // Если этот элемент не может поместиться в текущем контейнере

        if (weight[i] > bin_rem) {

            res++; // Используем новую корзину

            bin_rem = c - weight[i];

        }

        else

            bin_rem -= weight[i];

    }

    return res;

}

  
// Драйвер программы

int main()

{

    int weight[] = { 2, 5, 4, 7, 1, 3, 8 };

    int c = 10;

    int n = sizeof(weight) / sizeof(weight[0]);

    cout << "Number of bins required in Next Fit : "

         << nextFit(weight, n, c);

    return 0;

}

Джава

// Java программа для поиска номера
// корзин, необходимых для использования
// следующий алгоритм подбора.

class GFG {

  

    // Возвращает необходимое количество бинов

    // используя следующий алгоритм подбора онлайн

    static int nextFit(int weight[], int n, int c)

    {

  

        // Инициализируем результат (Количество бинов) и оставшиеся

        // емкость в текущей корзине

        int res = 0, bin_rem = c;

  

        // Размещаем предметы по одному

        for (int i = 0; i < n; i++) {

            // Если этот элемент не может поместиться в текущем контейнере

            if (weight[i] > bin_rem) {

                res++; // Используем новую корзину

                bin_rem = c - weight[i];

            }

            else

                bin_rem -= weight[i];

        }

        return res;

    }

  

    // Драйвер программы

    public static void main(String[] args)

    {

        int weight[] = { 2, 5, 4, 7, 1, 3, 8 };

        int c = 10;

        int n = weight.length;

        System.out.println("Number of bins required in Next Fit : " + nextFit(weight, n, c));

    }

}

  
// Этот код предоставлен 29AjayKumar

python3

# Реализация Python3 для вышеуказанного подхода

def nextfit(weight, c):

    res = 0

    rem = c

    for _ in range(len(weight)):

        if rem >= weight[_]:

            rem = rem - weight[_]

        else:

            res += 1

            rem = c - weight[_]

    return res

  
Код водителя

weight = [2, 5, 4, 7, 1, 3, 8]

c = 10

  

print("Number of bins required in Next Fit :"

                           nextfit(weight, c))

  
# Этот код предоставлен code_freak


Выход:

Number of bins required in Next Fit : 4

Next Fit — это простой алгоритм. Для обработки n элементов требуется только O (n) времени и O (1) дополнительного пространства.

Следующая аппроксимация приближена на 2, т. Е. Количество бинов, используемых этим алгоритмом, ограничено вдвое оптимальным. Рассмотрим любые две соседние корзины. Сумма предметов в этих двух корзинах должна быть> c; в противном случае NextFit поместил бы все элементы второй корзины в первую. То же самое относится ко всем другим корзинам. Таким образом, не более половины пространства тратится впустую, и поэтому Next Fit использует не более 2M корзин, если M оптимально.

2. Первая посадка:
При обработке следующего элемента отсканируйте предыдущие корзины по порядку и поместите элемент в первый подходящий лоток. Начните новую корзину, только если она не помещается ни в одну из существующих корзин.

// C ++ программа для поиска необходимого количества бинов
// алгоритм First Fit.
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает количество бинов, необходимое при первом подборе
// онлайн алгоритм

int firstFit(int weight[], int n, int c)

{

    // Инициализировать результат (Количество бинов)

    int res = 0;

  

    // Создать массив для хранения оставшегося места в бинах

    // может быть не более n корзин

    int bin_rem[n];

  

    // Размещаем предметы по одному

    for (int i = 0; i < n; i++) {

        // Найти первый контейнер, который может вместить

        // вес [я]

        int j;

        for (j = 0; j < res; j++) {

            if (bin_rem[j] >= weight[i]) {

                bin_rem[j] = bin_rem[j] - weight[i];

                break;

            }

        }

  

        // Если ни одна корзина не может вместить вес [i]

        if (j == res) {

            bin_rem[res] = c - weight[i];

            res++;

        }

    }

    return res;

}

  
// Драйвер программы

int main()

{

    int weight[] = { 2, 5, 4, 7, 1, 3, 8 };

    int c = 10;

    int n = sizeof(weight) / sizeof(weight[0]);

    cout << "Number of bins required in First Fit : "

         << firstFit(weight, n, c);

    return 0;

}

Выход:

Number of bins required in First Fit : 4

Приведенная выше реализация First Fit требует времени O (n 2 ), но First Fit может быть реализована за O (n Log n) времени с использованием самобалансирующихся деревьев бинарного поиска.

Если M — оптимальное количество ячеек, то First Fit никогда не использует больше, чем 1.7M ячеек. Таким образом, First Fit лучше, чем Next Fit, с точки зрения верхней границы количества бинов.

3. Лучшая подгонка:
Идея состоит в том, чтобы поместить следующий элемент в * самое трудное * место. То есть положите его в мусорное ведро, чтобы осталось наименьшее пустое пространство.

// C ++ программа для поиска необходимого количества бинов
// Алгоритм наилучшего соответствия.
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает количество бинов, необходимое для наилучшего соответствия
// онлайн алгоритм

int bestFit(int weight[], int n, int c)

{

    // Инициализировать результат (Количество бинов)

    int res = 0;

  

    // Создать массив для хранения оставшегося места в бинах

    // может быть не более n корзин

    int bin_rem[n];

  

    // Размещаем предметы по одному

    for (int i = 0; i < n; i++) {

        // Найти лучший контейнер, который можно разместить

        // вес [я]

        int j;

  

        // Инициализировать оставшееся минимальное пространство и индексировать

        // лучшего бина

        int min = c + 1, bi = 0;

  

        for (j = 0; j < res; j++) {

            if (bin_rem[j] >= weight[i] && bin_rem[j] - weight[i] < min) {

                bi = j;

                min = bin_rem[j] - weight[i];

            }

        }

  

        // Если ни одна корзина не может вместить вес [i],

        // создаем новую корзину

        if (min == c + 1) {

            bin_rem[res] = c - weight[i];

            res++;

        }

        else // Присваиваем элемент на лучшее место

            bin_rem[bi] -= weight[i];

    }

    return res;

}

  
// Драйвер программы

int main()

{

    int weight[] = { 2, 5, 4, 7, 1, 3, 8 };

    int c = 10;

    int n = sizeof(weight) / sizeof(weight[0]);

    cout << "Number of bins required in Best Fit : "

         << bestFit(weight, n, c);

    return 0;

}

Выход:

Number of bins required in Best Fit : 4

Наилучшее соответствие также может быть реализовано за O (n Log n), используя деревья самобалансирующегося бинарного поиска.

Если M — это оптимальное количество ячеек, то Best Fit никогда не использует больше чем 1.7M ячеек. Таким образом, Best Fit — то же самое, что First Fit, и лучше, чем Next Fit, с точки зрения верхней границы количества ячеек.

Автономные алгоритмы
В оффлайновой версии у нас есть все элементы заранее. К сожалению, автономная версия также является NP Complete, но у нас есть лучший примерный алгоритм для нее. First Fit Decreasing использует не более (4M + 1) / 3 бункеров, если оптимальным является M.

4. Первая посадка уменьшается:
Проблема с онлайн-алгоритмами заключается в том, что упаковка больших предметов затруднена, особенно если они происходят поздно в последовательности. Мы можем обойти это, * отсортировав * последовательность ввода и поместив сначала большие элементы. С сортировкой мы получаем First Fit Decreasing и Best Fit Decreasing, как офлайновые аналоги онлайн First Fit и Best Fit.

// C ++ программа для поиска необходимого количества бинов
// Алгоритм уменьшения первой подгонки.
#include <bits/stdc++.h>

using namespace std;

  
/ * Копировать firstFit () сверху * /

  
// Возвращает количество бинов, необходимое при первом подборе
// уменьшение автономного алгоритма

int firstFitDec(int weight[], int n, int c)

{

    // Сначала сортируем все веса в порядке убывания

    sort(weight, weight + n, std::greater<int>());

  

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

    return firstFit(weight, n, c);

}

  
// Драйвер программы

int main()

{

    int weight[] = { 2, 5, 4, 7, 1, 3, 8 };

    int c = 10;

    int n = sizeof(weight) / sizeof(weight[0]);

    cout << "Number of bins required in First Fit "

         << "Decreasing : " << firstFitDec(weight, n, c);

    return 0;

}

Выход:

Number of bins required in First Fit Decreasing : 3

Уменьшение при первой подгонке дает наилучший результат для выборки, поскольку элементы сортируются первыми.

Уменьшение первого соответствия также может быть реализовано за время O (n Log n) с использованием самобалансирующихся деревьев двоичного поиска.

Эта статья предоставлена Dheeraj Gupta . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

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

Проблема упаковки бункера (свести к минимуму количество используемых бинов)

0.00 (0%) 0 votes