"破解编码访谈(第五版)":9.10框堆叠

Question

你有一堆n个盒子,宽度为wi,高度为hi,深度为di.如果堆叠中的每个盒子的宽度,高度和深度都大于或等于其上方的盒子,则盒子不能旋转并且只能堆叠在一起.实现一种方法来构建最高的堆栈,其中堆栈的高度是每个盒子高度的总和.

我知道有几篇文章要讨论使用动态编程来解决它.由于我想编写递归代码,我编写了以下代码:

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);

在该函数中highest_stack,有一行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? 

我不认为我的代码很优雅.谢谢

Answer 1

我会制作一个有向图,其中节点是方框,边缘从一个盒子到一个盒子,可以放在它上面.然后我会使用最长路径算法来找到解决方案.