Vấn đề xếp hộp

Trong bài toán này đưa ra một tập hợp các hộp khác nhau, chiều dài, chiều rộng và chiều rộng có thể khác nhau đối với các hộp khác nhau. Nhiệm vụ của chúng ta là tìm một chồng các hộp này, có chiều cao càng nhiều càng tốt. Chúng ta có thể xoay bất kỳ hộp nào theo ý muốn. Nhưng có một quy tắc cần duy trì.

Người ta có thể đặt một hộp lên một hộp khác nếu diện tích của bề mặt trên cùng của hộp dưới cùng lớn hơn diện tích dưới của hộp trên cùng.

Đầu vào và Đầu ra

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

Thuật toán

maxHeight(boxList, n)

Đầu vào - Danh sách các hộp khác nhau, số lượng hộp.

Đầu ra - chiều cao tối đa được tìm thấy bằng cách xếp chồng các hộp.

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

Ví dụ

#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;
}

Đầu ra

The maximum possible height of box stack is: 60