ปัญหาการซ้อนกล่อง (Box Stacking Problem)

กำหนดชุดกล่องที่มีขนาดต่างกัน (ความยาว ความกว้าง ความสูง) ต้องการหาการซ้อนกล่องที่ให้ความสูงรวมมากที่สุด สามารถหมุนกล่องได้ตามต้องการ แต่มีกติกาว่า พื้นที่ผิวด้านบนของกล่องล่างต้องกว้างกว่าพื้นที่ผิวด้านล่างของกล่องบน

การรับค่าและแสดงผล

Input: รายการกล่อง (ความยาว, ความกว้าง, ความสูง)
{ (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
  สร้างอาร์เรย์ rotation ขนาด 3n (แต่ละกล่องหมุนได้ 3 ท่า)
  index := 0
  
  for ทุกกล่อง i ใน boxList do
    // ท่าที่ 1
    rot[index].len := boxList[i].len
    rot[index].hei := max(boxList[i].hei, boxList[i].bre)
    rot[index].bre := min(boxList[i].hei, boxList[i].bre)
    index++
    
    // ท่าที่ 2
    rot[index].len := boxList[i].bre
    rot[index].hei := max(boxList[i].len, boxList[i].hei)
    rot[index].bre := min(boxList[i].len, boxList[i].hei)
    index++
    
    // ท่าที่ 3
    rot[index].len := boxList[i].hei
    rot[index].hei := max(boxList[i].len, boxList[i].bre)
    rot[index].bre := min(boxList[i].len, boxList[i].bre)
    index++
  done
  
  n := 3n
  เรียง rot ตามความสูง (hei) จากมากไปน้อย
  
  กำหนดอาร์เรย์ maxHeightTemp
  for i := 0 ถึง n-1 do
    maxHeightTemp[i] := rot[i].len
  done
  
  for i := 1 ถึง n-1 do
    for j := 0 ถึง i-1 do
      if rot[i].bre < rot[j].bre AND rot[i].hei < rot[j].hei AND
         maxHeightTemp[i] < maxHeightTemp[j] + rot[i].len then
        maxHeightTemp[i] := maxHeightTemp[j] + rot[i].len
      end if
    done
  done
  
  maxHeight := -1
  for i := 0 ถึง n-1 do
    if maxHeight < maxHeightTemp[i] then maxHeight := maxHeightTemp[i]
  done
  
  return maxHeight
End

ตัวอย่างโค้ด (C++)

#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];
  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].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++;
    
    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;
  sort(rotation, rotation+n, compare);
  
  int maxHTemp[n];
  for (int i = 0; i < n; i++) maxHTemp[i] = rotation[i].length;
  
  for (int i = 1; i < n; i++)
    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++)
    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);
}

ผลลัพธ์

The maximum possible height of box stack is: 60