Рубрики

Проблема укладки коробок | DP-22

Вам предоставляется набор из n типов прямоугольных трехмерных блоков, где i-й блок имеет высоту h (i), ширину w (i) и глубину d (i) (все действительные числа). Вы хотите создать стопку коробок, которая будет максимально высокой , но вы можете сложить ящик только над другим, если размеры двухмерного основания нижнего ящика строго превышают размеры двухмерного основания верхнего ящика. Конечно, вы можете вращать коробку так, чтобы любая сторона функционировала как ее основа. Также допустимо использовать несколько экземпляров одного и того же типа ящика.
Источник: http://people.csail.mit.edu/bdean/6.046/dp/ . Ссылка также имеет видео для объяснения решения.

Проблема с укладкой в коробку является разновидностью проблемы LIS . Нам нужно построить стек с максимальной высотой.

Ниже приведены ключевые моменты, которые следует отметить в постановке задачи:
1) Ящик можно поместить поверх другого ящика, только если ширина и глубина верхнего помещенного ящика меньше ширины и глубины нижнего ящика соответственно.
2) Мы можем вращать боксы так, чтобы ширина была меньше глубины. Например, если есть поле с размерами {1x2x3}, где 1 — высота, 2 × 3 — основание, то возможны три варианта: {1x2x3}, {2x1x3} и {3x1x2}
3) Мы можем использовать несколько экземпляров ящиков. Это означает, что мы можем иметь два разных поворота коробки как часть нашего стека максимальной высоты.

Ниже приводится решение, основанное на решении ДП проблемы LIS .

1) Генерация всех 3 поворотов всех коробок. Размер массива вращения становится в 3 раза больше размера исходного массива. Для простоты мы рассматриваем глубину как всегда меньшую или равную ширине.

2) Сортировать сгенерированные выше 3n ящиков в порядке убывания базовой площади.

3) После сортировки блоков проблема та же, что и в LIS, с оптимальным свойством субструктуры.
MSH (i) = максимально возможная высота стека с полем i на вершине стека
MSH (i) = {Макс (MSH (j)) + высота (i)}, где j <i и ширина (j)> ширина (i) и глубина (j)> глубина (i).
Если такого j нет, то MSH (i) = высота (i)

4) Чтобы получить общую максимальную высоту, мы возвращаем max (MSH (i)), где 0 <i <n

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

C ++

/ * Реализация задачи динамического программирования Box Stacking * /
#include<stdio.h>
#include<stdlib.h>

  
/ * Представление коробки * /

struct Box

{

  // h -> высота, w -> ширина, d -> глубина

  int h, w, d;  // для простоты решения всегда держим w <= d

};

  
// Полезная функция для получения минимум двух целых чисел

int min (int x, int y)

{ return (x < y)? x : y; }

  
// Полезная функция для получения максимум двух целых чисел

int max (int x, int y)

{ return (x > y)? x : y; }

  
/ * Следующая функция необходима для библиотечной функции qsort (). Мы

   используйте qsort () для сортировки блоков в порядке убывания базовой области.

   Обратитесь по следующей ссылке за помощью qsort () и сравните ()

   http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/ * /

int compare (const void *a, const void * b)

{

    return ( (*(Box *)b).d * (*(Box *)b).w ) -

           ( (*(Box *)a).d * (*(Box *)a).w );

}

  
/ * Возвращает высоту самого высокого стека, который может быть

   формируется с заданным типом ящиков * /

int maxStackHeight( Box arr[], int n )

{

   / * Создать массив всех вращений заданных ящиков

      Например, для коробки {1, 2, 3} мы рассмотрим три

      экземпляры {{1, 2, 3}, {2, 1, 3}, {3, 1, 2}} * /

   Box rot[3*n];

   int index = 0;

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

   {

      // Копируем оригинальную коробку

      rot[index].h = arr[i].h;

      rot[index].d = max(arr[i].d, arr[i].w);

      rot[index].w = min(arr[i].d, arr[i].w);

      index++;

  

      // Первый поворот ящика

      rot[index].h = arr[i].w;

      rot[index].d = max(arr[i].h, arr[i].d);

      rot[index].w = min(arr[i].h, arr[i].d);

      index++;

  

      // Второе вращение коробки

      rot[index].h = arr[i].d;

      rot[index].d = max(arr[i].h, arr[i].w);

      rot[index].w = min(arr[i].h, arr[i].w);

      index++;

   }

  

   // Теперь количество ящиков 3n

   n = 3*n;

  

   / * Сортировать массив 'rot []' по возрастанию

      базовой площади * /

   qsort (rot, n, sizeof(rot[0]), compare);

  

   // Раскомментируем две строки для печати всех поворотов

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

   // printf ("% dx% dx% d / n", rot [i] .h, rot [i] .w, rot [i] .d);

  

   / * Инициализировать значения msh для всех индексов

      msh [i] -> Максимально возможная высота стека с полем i сверху * /

   int msh[n];

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

      msh[i] = rot[i].h;

  

   / * Рассчитать оптимизированные значения msh снизу вверх * /

   for (int i = 1; i < n; i++ )

      for (int j = 0; j < i; j++ )

         if ( rot[i].w < rot[j].w &&

              rot[i].d < rot[j].d &&

              msh[i] < msh[j] + rot[i].h

            )

         {

              msh[i] = msh[j] + rot[i].h;

         }

  

  

   / * Выберите максимум всех значений msh * /

   int max = -1;

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

      if ( max < msh[i] )

         max = msh[i];

  

   return max;

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

  Box arr[] = { {4, 6, 7}, {1, 2, 3}, {4, 5, 6}, {10, 12, 32} };

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

  

  printf("The maximum possible height of stack is %d\n",

         maxStackHeight (arr, n) );

  

  return 0;

}

Джава

/ * Реализация динамического программирования
проблемы укладки ящиков в Java * /

import java.util.*;

  

public class GFG {

      

    / * Представление коробки * /

    static class Box implements Comparable<Box>{

      

        // h -> высота, w -> ширина,

        // d -> глубина

        int h, w, d, area;

          

        // для простоты решения,

        // всегда держим w <= d

  

        / * Конструктор для инициализации объекта * /

        public Box(int h, int w, int d) {

            this.h = h;

            this.w = w;

            this.d = d;

        }

          

        / * Сортировать массив блоков на основе

        площади в порядке убывания площади * /

        @Override

        public int compareTo(Box o) {

            return o.area-this.area;

        }

    }

  

    / * Возвращает высоту самого высокого

    стек, который может быть сформирован с помощью Give

    тип ящиков * /

    static int maxStackHeight( Box arr[], int n){

          

        Box[] rot = new Box[n*3];

          

        / * Создан новый массив ящиков -

        учитывая все 3 возможных поворота,

        с шириной всегда больше равной

        по ширине * /

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

            Box box = arr[i];

              

            / * Оригинальная Коробка * /

            rot[3*i] = new Box(box.h, Math.max(box.w,box.d), 

                                    Math.min(box.w,box.d));

              

            / * Первое вращение коробки * /

            rot[3*i + 1] = new Box(box.w, Math.max(box.h,box.d), 

                                       Math.min(box.h,box.d));

              

            / * Второе вращение коробки * /

            rot[3*i + 2] = new Box(box.d, Math.max(box.w,box.h),

                                       Math.min(box.w,box.h));

        }

          

        / * Расчет базовой площади

        каждая из коробок. * /

        for(int i = 0; i < rot.length; i++)

            rot[i].area = rot[i].w * rot[i].d;

          

        / * Сортировка ящиков по основаниям

        площади в не возрастающем порядке. * /

        Arrays.sort(rot);

          

        int count = 3 * n;

          

        / * Инициализировать значения msh для всех

        индексы

        msh [i] -> максимально возможная высота стека

                   с коробкой я сверху * /

        int[]msh = new int[count];

        for (int i = 0; i < count; i++ )

            msh[i] = rot[i].h;

          

        / * Вычисления оптимизированы Msh []

        значения снизу вверх * /

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

            msh[i] = 0;

            Box box = rot[i];

            int val = 0;

              

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

                Box prevBox = rot[j];

                if(box.w < prevBox.w && box.d < prevBox.d){

                    val = Math.max(val, msh[j]);

                }

            }

            msh[i] = val + box.h;

        }

          

        int max = -1;

          

        / * Выберите максимум всех значений msh * /

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

            max = Math.max(max, msh[i]);

        }

          

        return max;

    }

      

    / * Программа драйвера для проверки вышеуказанной функции * /

    public static void main(String[] args) {

          

        Box[] arr = new Box[4];

        arr[0] = new Box(4, 6, 7);

        arr[1] = new Box(1, 2, 3);

        arr[2] = new Box(4, 5, 6);

        arr[3] = new Box(10, 12, 32);

          

        System.out.println("The maximum possible "+

                           "height of stack is "

                           maxStackHeight(arr,4));

    }

}

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

python3

# Динамическое программирование реализации
# Количество проблем с укладкой ящиков

class Box:

      

    # Представление коробки

    def __init__(self, h, w, d):

        self.h = h

        self.w = w

        self.d = d

  

    def __lt__(self, other):

        return self.d * self.w < other.d * other.w

  

def maxStackHeight(arr, n):

  

    # Создать массив всех вращений

    # данные ящики. Например, для поля {1, 2, 3}

    # рассмотрим три экземпляра {{1, 2, 3},

    # {2, 1, 3}, {3, 1, 2}}

    rot = [Box(0, 0, 0) for _ in range(3 * n)]

    index = 0

  

    for i in range(n):

  

        # Скопируйте оригинальную коробку

        rot[index].h = arr[i].h

        rot[index].d = max(arr[i].d, arr[i].w)

        rot[index].w = min(arr[i].d, arr[i].w)

        index += 1

  

        # Первое вращение коробки

        rot[index].h = arr[i].w

        rot[index].d = max(arr[i].h, arr[i].d)

        rot[index].w = min(arr[i].h, arr[i].d)

        index += 1

  

        # Второе вращение коробки

        rot[index].h = arr[i].d

        rot[index].d = max(arr[i].h, arr[i].w)

        rot[index].w = min(arr[i].h, arr[i].w)

        index += 1

  

    # Теперь количество ящиков 3n

    n *= 3

  

    # Сортировать массив 'rot []' по возрастанию

    # порядок базовой площади

    rot.sort(reverse = True)

  

    # Раскомментируйте следующие две строки для печати

    # все вращения

    # для i в диапазоне (n):

    # print (rot [i] .h, 'x', rot [i] .w, 'x', rot [i] .d)

  

    # Инициализировать значения msh для всех индексов

    # msh [i] -> Максимально возможная высота стека

    # с полем я сверху

    msh = [0] * n

  

    for i in range(n):

        msh[i] = rot[i].h

  

    # Вычислить оптимизированные значения Msh

    # снизу вверх

    for i in range(1, n):

        for j in range(0, i):

            if (rot[i].w < rot[j].w and 

                rot[i].d < rot[j].d):

                if msh[i] < msh[j] + rot[i].h:

                    msh[i] = msh[j] + rot[i].h

  

    maxm = -1

    for i in range(n):

        maxm = max(maxm, msh[i])

  

    return maxm

  
Код водителя

if __name__ == "__main__":

    arr = [Box(4, 6, 7), Box(1, 2, 3),

           Box(4, 5, 6), Box(10, 12, 32)]

    n = len(arr)

    print("The maximum possible height of stack is",

           maxStackHeight(arr, n))

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


Выход:

The maximum possible height of stack is 60

В вышеприведенной программе заданы поля ввода: {4, 6, 7}, {1, 2, 3}, {4, 5, 6}, {10, 12, 32}. Ниже приведены все повороты коробок в порядке убывания базовой площади.

   10 x 12 x 32
   12 x 10 x 32
   32 x 10 x 12
   4 x 6 x 7
   4 x 5 x 6
   6 x 4 x 7
   5 x 4 x 6
   7 x 4 x 6
   6 x 4 x 5
   1 x 2 x 3
   2 x 1 x 3
   3 x 1 x 2

Высота 60 получается с помощью блоков {{ 3 , 1, 2}, { 1 , 2, 3}, { 6 , 4, 5}, { 4 , 5, 6}, { 4 , 6, 7}, { 32 , 10, 12}, { 10 , 12, 32}}

Сложность времени: O (n ^ 2)
Вспомогательное пространство: O (n)

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

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

Проблема укладки коробок | DP-22

0.00 (0%) 0 votes