algorithm - “cracking the coding interview(fifth edition)” : 9. 10盒堆叠

Question

You have a stack of n boxes, with widths wi, heights hi, and depths di. The boxes cannot be rotated and can only be stacked on top of one another if each box in the stack larger than or equal to the box above it in width, height, and depth. Implement a method to build the tallest stack possible, where the height of a stack is the sum of the heights of each box.

我知道有几篇文章讨论使用动态规划来解决它。由于我想练习编写递归代码，所以我编写了以下代码:

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;

the output is: 1 2 4; 1 2; 1, 1 4;

如果我不评论no_suitable = true;

the output is: 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? 

I don't think my code is elegant. Thanks

Answer 1

我会制作一个有向图，其中节点是框，边从一个框到另一个可以放在它上面的框。然后我会使用 longest path algorithm找到解决方案。