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

/ * Реализация задачи динамического программирования 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

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

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