ボックススタッキング問題を動的計画法で解く方法とC++実装例

この問題では、複数の異なる箱が与えられます。それぞれの箱は長さ・幅・高さが異なる場合があります。目的は、これらの箱を積み上げて、可能な限り高い塔を作ることです。箱は自由に回転できますが、守らなければならないルールが1つあります。

ある箱を別の箱の上に置けるのは、下の箱の上面の面積が、上の箱の底面の面積よりも大きい場合のみです。

入力と出力

入力:
箱のリストが与えられます。各箱は (長さ, 幅, 高さ) で表されます。
{ (4, 6, 7), (1, 2, 3), (4, 5, 6), (10, 12, 32) }
出力:
箱の積み上げの最大高さ: 60

アルゴリズム

maxHeight(boxList, n)

入力 − 異なる箱のリストと、箱の個数。

出力 − 箱を積み上げることで得られる最大の高さ。

このアルゴリズムのポイントは、各箱について3通りの回転を生成し、それぞれを「積み上げ時の高さ」と「底面の2辺」に正規化して扱う点です。箱の数を n とすると、回転を含めた配置の総数は 3n になります。これらを底面の基準となる辺の降順にソートし、最長増加部分列（LIS）と同様の動的計画法で最適な積み上げ高さを求めます。

開始
    サイズ 3n の回転配列 rot を定義する
    index := 0

    boxList 内のすべての箱 i に対して、以下を実行する
        // 箱の元の向き
        rot[index].len := boxList[i].len
        rot[index].hei := boxList[i].hei と boxList[i].bre の最大値
        rot[index].bre := boxList[i].hei と boxList[i].bre の最小値
        index := index + 1

        // 1回目の回転後の寸法
        rot[index].len := boxList[i].bre
        rot[index].hei := boxList[i].len と boxList[i].hei の最大値
        rot[index].bre := boxList[i].len と boxList[i].hei の最小値
        index := index + 1

        // 2回目の回転後の寸法
        rot[index].len := boxList[i].hei
        rot[index].hei := boxList[i].len と boxList[i].bre の最大値
        rot[index].bre := boxList[i].len と boxList[i].bre の最小値
        index := index + 1

    n := 3n
    rot リストを底面の基準となる辺の降順にソートする
    maxHeightTemp 配列を定義する

    i := 1 から n-1 まで、以下を繰り返す
        j := 0 から i-1 まで、以下を繰り返す
            もし rot[i].bre < rot[j].bre かつ
               rot[i].hei < rot[j].hei かつ
               maxHeightTemp[i] < maxHeightTemp[j] + rot[i].len ならば
                maxHeightTemp[i] := maxHeightTemp[j] + rot[i].len
        繰り返し終了
    繰り返し終了

    maxHeight := -1
    i := 0 から n-1 まで、以下を繰り返す
        もし maxHeight < maxHeightTemp[i] ならば
            maxHeight := maxHeightTemp[i]
    繰り返し終了
    maxHeight を返す
終了

回転の生成に O(n)、ソートに O(n log n)、動的計画法の本体に O(n²) かかるため、全体の時間計算量は O(n²) となります。

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];    // 1つの箱は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++;

        // 1回目の回転後の寸法
        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++;

        // 2回目の回転後の寸法
        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;    // 各箱が3つの回転を持つため、n を 3n に更新

    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++ )    // 最適な積み上げ高さを求める
        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<<"箱の積み上げの最大高さ: " << maxHeight (arr, n) << endl;
}

出力

箱の積み上げの最大高さ: 60