盒子堆叠问题

data structuredynamic programmingalgorithms

在这个问题中，给出了一组不同的盒子，不同盒子的长度、宽度和宽度可能不同。我们的任务是找到这些盒子的堆叠，其高度尽可能大。我们可以随意旋转任何盒子。但有一个规则需要遵守。

如果底部盒子的顶面面积大于顶部盒子的下面积，则可以将一个盒子放在另一个盒子上。

输入和输出

输入:
给出了一个盒子列表。每个盒子都用(长度、宽度、高度)表示。
{ (4, 6, 7), (1, 2, 3), (4, 5, 6), (10, 12, 32) }
输出:
箱子堆叠的最大可能高度为: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;    //按高度降序对框进行排序
}

int maxHeight( Box boxList[], int n ) {
   Box rotation[3*n];    //一个框可以旋转为 3 种类型，因此有 3n 次旋转
   int index = 0;

   for (int i = 0; i < n; i++) {
      //存储框的初始位置
      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++;

      //第一次旋转后的尺寸
      rotation[index].height = max(boxList[i].length, boxList[i].height);
      rotation[index].bredth = min(boxList[i].length, boxList[i].height);
      index++;        
   
      //第二次旋转后的尺寸
      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;    //将 n 设置为 3n，每个盒子旋转 3 次

   sort(rotation, rotation+n, compare);    //按降序对旋转数组进行排序

   int maxHTemp[n];    //如果第 i 个盒子堆叠，则临时最大高度

   for (int i = 0; i < n; i++ )
      maxHTemp[i] = rotation[i].length;
   
   for (int i = 1; i < n; i++ )    //找到优化的堆叠高度
     对于 (int j = 0; j < i; j++ )
          如果 ( 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++ )    //从所有临时高度中找出最大高度
         
      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<<"盒子堆叠的最大可能高度为:" << maxHeight (arr, n) << endl;
}