2

你有一堆 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?

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

4

2 回答 2

7

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

于 2012-10-03T23:30:57.570 回答
0

将关系设计为一组盒子数组。(Set[]) 即每个位置都有一个盒子数组。

用索引初始化每个框。

对于可以放置在当前框（box[i]）上方的每个框复选框，将其添加到集合数组中的集合中，即 set[i].add(box)

用可以放在上面的盒子运行DFS（相邻的作用）

维护一个marked[]、count[] 和boxTo[] 盒子数组。

遍历计数数组并找到最大值。

使用 boxTo[] 数组遍历底部框。

于 2014-05-30T21:30:59.443 回答