2

幅 wi、高さ hi、深さ di の n 個のボックスのスタックがあります。ボックスを回転させることはできず、スタック内の各ボックスの幅、高さ、奥行きがその上のボックスよりも大きいか等しい場合にのみ、互いに積み重ねることができます。スタックの高さが各ボックスの高さの合計である、可能な限り高いスタックを構築するメソッドを実装します。

動的計画法を使用してそれを解決することについて話し合う記事がいくつかあることは知っています。再帰コードを書く練習をしたいので、次のコードを書きました。

const int not_possible = 999999;

class box{
public:
    int width;
    int depth;
    int height;
    box(int h=not_possible, int d=not_possible, int w=not_possible):
        width(w), depth(d), height(h) {}
};


bool check_legal(box lower, box upper){
    return (upper.depth<lower.depth) && 
           (upper.height<lower.height) &&
           (upper.width<lower.width);
}

void highest_stack(const vector<box>& boxes, bool* used, box cur_level, int num_boxes, int height, int& max_height)
{
    if(boxes.empty())
        return;

    bool no_suitable = true;
    for(int i = 0; i < num_boxes; ++i){
        box cur;
        if(!(*(used+i)) && check_legal(cur_level, boxes[i])){
            no_suitable = false;
            cur = boxes[i];
            *(used+i) = true;
            highest_stack(boxes, used, cur, num_boxes, height+cur.height, max_height);
            *(used+i) = false;

                    no_suitable = true;
        }
    }

    if(no_suitable){
        cout << height << endl; //for debug
        if(height > max_height)
            max_height = height;
            return;
    }
}

多くの例を使用してテストしました。例えば：

boxes.push_back(box(4,12,32));
boxes.push_back(box(1,2,3));
boxes.push_back(box(2,5,6));
highest_stack(boxes, used, cur, boxes.size(), 0, max_height);

functionhighest_stackには、出力用の 1 行がありcout << height << endl;ます。コメントしたらno_suitable = true;

出力は次のとおりです。1 2 4; 1 2; 1、1 4;

コメントしないとno_suitable = true;

出力は次のとおりです。1 2 4; 2 4; 4; 1 2; 2; 1; 1 4; 0

どちらも 7 という正しい結果を出すことができます。

My question is:
(1) Can anyone help me verify my solution?
(2) Is there any more elegant recursive code for this problem?

私のコードはエレガントではないと思います。ありがとう

4

2 に答える 2

7

ノードがボックスで、エッジがボックスからその上に配置できるボックスに移動する有向グラフを作成します。次に、最長パス アルゴリズムを使用して解決策を見つけます。

于 2012-10-03T23:30:57.570 に答える
0

ボックスのセット配列 (Set[]) としてリレーションを設計します。つまり、各位置にはボックスの配列があります。

各ボックスをインデックスで初期化します。

現在のボックス (box[i]) の上に配置できるボックス チェック ボックスごとに、セット配列のセットに追加します。つまり、set[i].add(box)

上に置ける箱でDFSを走らせる（隣接の役割）

ボックスのmarked[]、count[]、boxTo[]配列を維持します。

count 配列を調べて、最大値を見つけます。

boxTo[] 配列を使用して、一番下のボックスまでたどります。

于 2014-05-30T21:30:59.443 に答える