Bài toán xếp hộp (Box Stacking Problem)

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

Ta có thể đặt một hộp lên hộp khác nếu diện tích mặt trên của hộp dưới lớn hơn diện tích mặt dưới của hộp trên.

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

Đầu vào: Danh sách các hộp. Mỗi hộp ký hiệu bằng (chiều dài, chiều rộng, chiều cao).
{ (4, 6, 7), (1, 2, 3), (4, 5, 6), (10, 12, 32) }
Đầu ra: Chiều cao tối đa có thể của chồng hộp là: 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 tìm được bằng cách xếp chồng hộp.
Bắt đầu
  định nghĩa mảng xoay rot kích thước 3n
  index := 0
  với mọi hộp i trong boxList, thực hiện
    rot[index].len := boxList[i].len
    rot[index].hei := max của boxList[i].hei và boxList[i].bre
    rot[index].bre := min của boxList[i].hei và boxList[i].bre
    index := index + 1
    rot[index].len := boxList[i].bre
    rot[index].hei := max của boxList[i].len và boxList[i].hei
    rot[index].bre := min của boxList[i].len và boxList[i].hei
    index := index + 1
    rot[index].len := boxList[i].hei
    rot[index].hei := max của boxList[i].len và boxList[i].bre
    rot[index].bre := min của boxList[i].len và boxList[i].bre
    index := index + 1
    n := 3n
    sắp xếp danh sách rot
    định nghĩa mảng maxHeightTemp
    với i := 1 đến n-1, thực hiện
      với j := 0 đến i-1, thực hiện
        nếu rot[i].bre < rot[j].bre VÀ
          rot[i].hei < rot[j].hei VÀ
          maxHeightTemp[i] < maxHeightTemp + rot[i].len thì
          maxHeightTemp[i] := maxHeightTemp[j] + rot[i].len
      kết thúc
    kết thúc
    maxHeight := -1
    với i := 0 đến n-1, thực hiện
      nếu maxHeight < maxHeightTemp[i] thì
        maxHeight := maxHeightTemp[i]
      kết thúc
    kết thúc
  trả về maxHeight
Kết thúc

Ví dụ (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; // để sắp xếp hộp theo thứ tự giảm dần chiều cao
}

int maxHeight(Box boxList[], int n) {
  Box rotation[3*n]; // một hộp có thể xoay 3 kiểu, nên có 3n số lần xoay
  int index = 0;
  
  for (int i = 0; i < n; i++) {
    // lưu vị trí ban đầu của hộp
    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++;
    
    // kích thước sau lần xoay đầu tiên
    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++;
    
    // Kích thước sau lần xoay thứ hai
    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; // đặt n thành 3n cho 3 lần xoay của mỗi hộp
  sort(rotation, rotation+n, compare); // sắp xếp mảng xoay theo thứ tự giảm dần
  
  int maxHTemp[n]; // chiều cao tối đa tạm thời nếu hộp thứ i được xếp
  for (int i = 0; i < n; i++)
    maxHTemp[i] = rotation[i].length;
  
  for (int i = 1; i < n; i++) // tìm chiều cao xếp chồng tối ưu
    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++) // tìm chiều cao tối đa từ tất cả chiều cao tạm thờ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) << endl;
}

Đầu ra

The maximum possible height of box stack is: 60