상자 쌓기 문제

이 문제에서는 다른 상자 세트가 제공되며 길이, 너비 및 너비는 상자마다 다를 수 있습니다. 우리의 임무는 가능한 한 높이가 높은 이러한 상자 더미를 찾는 것입니다. 원하는 대로 상자를 회전할 수 있습니다. 하지만 지켜야 할 규칙이 있습니다.

하단 상자의 상단 표면 면적이 상단 상자의 하단 면적보다 크면 다른 상자에 상자를 놓을 수 있습니다.

입력 및 출력

Input:
A list of boxes is given. Each box is denoted by (length, bredth, height).
{ (4, 6, 7), (1, 2, 3), (4, 5, 6), (10, 12, 32) }
Output:
The maximum possible height of box stack is: 60

알고리즘

maxHeight(boxList, n)

입력 - 다른 상자 목록, 상자 수.

출력 - 상자를 쌓아서 찾은 최대 높이입니다.

Begin
   define rotation array rot of size 3n.
   index := 0

   for all boxes i, in the boxList, do
      rot[index].len := boxList[i].len
      rot[index].hei := maximum of boxList[i].hei and boxList[i].bre
      rot[index].bre := minimum of boxList[i].hei and boxList[i].bre
      index := index + 1

      rot[index].len := boxList[i].bre
      rot[index].hei := maximum of boxList[i].len and boxList[i].hei
      rot[index].bre := minimum of boxList[i].len and boxList[i].hei
      index := index + 1

      rot[index].len := boxList[i].hei
      rot[index].hei := maximum of boxList[i].len and boxList[i].bre
      rot[index].bre := minimum of boxList[i].len and boxList[i].bre
      index := index + 1

      n := 3n
      sort the rot list
      define maxHeightTemp array

      for i := 1 to n-1, do
         for j := 0 to i-1, do
            if rot[i].bre < rot[j].bre AND
               rot[i].hei < rot[j].hei AND
               maxHeightTemp[i] < maxHeightTemp + rot[i].len, then
               maxHeightTemp[i] := maxHeightTemp[j] +
               rot[i].len
         done
      done

      maxHeight := -1
      for i := 0 to n-1, do
         if maxHeight < maxHeightTemp[i], then
            maxHeight := maxHeightTemp[i]
      done
   done
   return maxHeight
End

예

#include<iostream>
#include<algorithm>
using namespace std;

struct Box {
   int length, bredth, height;
};

int min (int x, int y) {
   return (x < y)? x : y;
}

int max (int x, int y) {
   return (x > y)? x : y;
}

bool compare(Box b1, Box b2) {
   return b1.height > b2.height;    //to sort the box as descending order of height
}

int maxHeight( Box boxList[], int n ) {
   Box rotation[3*n];    //a box can be rotared as 3 type, so there is 3n number of rotations
   int index = 0;

   for (int i = 0; i < n; i++) {
      //store initial position of the box
      rotation[index].length = boxList[i].length;
      rotation[index].height = max(boxList[i].height, boxList[i].bredth);
      rotation[index].bredth = min(boxList[i].height, boxList[i].bredth);
      index++;

      //dimention after first rotation
      rotation[index].length = boxList[i].bredth;
      rotation[index].height = max(boxList[i].length, boxList[i].height);
      rotation[index].bredth = min(boxList[i].length, boxList[i].height);
      index++;        
   
      //Dimention after second rotation
      rotation[index].length = boxList[i].height;
      rotation[index].height = max(boxList[i].length, boxList[i].bredth);
      rotation[index].bredth = min(boxList[i].length, boxList[i].bredth);
      index++;
   }

   n = 3*n;    //set n as 3n for 3 rotations of each boxes

   sort(rotation, rotation+n, compare);    //sort rotation array as descending order

   int maxHTemp[n];    //temporary max height if ith box is stacked

   for (int i = 0; i < n; i++ )
      maxHTemp[i] = rotation[i].length;
   
   for (int i = 1; i < n; i++ )    //find optimized stack height
      for (int j = 0; j < i; j++ )
         if ( rotation[i].bredth < rotation[j].bredth && rotation[i].height < rotation[j].height
            && maxHTemp[i] < maxHTemp[j] + rotation[i].length) {
            maxHTemp[i] = maxHTemp[j] + rotation[i].length;
         }
   int maxHeight = -1;
   for ( int i = 0; i < n; i++ )    //find the maximum height from all temporary heights
         
      if ( maxHeight < maxHTemp[i] )
         maxHeight = maxHTemp[i];
         
   return maxHeight;
}

int main() {
   Box arr[] = { {4, 6, 7}, {1, 2, 3}, {4, 5, 6}, {10, 12, 32} };
   int n = 4;
   cout<<"The maximum possible height of box stack is: " << maxHeight (arr, n) << endl;
}

출력

The maximum possible height of box stack is: 60