美文网首页
每日一题之堆箱子

每日一题之堆箱子

作者: this_is_for_u | 来源:发表于2020-04-24 22:33 被阅读0次

    题目:堆箱子

    堆箱子。给你一堆n个箱子,箱子宽 wi、深 di、高 hi。箱子不能翻转,将箱子堆起来时,下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法,搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。

    输入使用数组[wi, di, hi]表示每个箱子。

    示例1:

    输入:box = [[1, 1, 1], [2, 2, 2], [3, 3, 3]]
    输出:6
    

    示例2:

    输入:box = [[1, 1, 1], [2, 3, 4], [2, 6, 7], [3, 4, 5]]
    输出:10
    

    提示:

    1. 箱子的数目不大于3000个。

    分析

    这题在回溯类型下,但无奈用回溯方法会超时,剪枝太麻烦,就使用了动态规划方法,首先选择 一个维度对输入box排序,用dp保存当前节点在底部的最大高度,见代码

    代码

    class Solution {
    public:
        int pileBox(vector<vector<int>>& box) {
            // 首先对输入box选择一个维度排序
            std::sort(box.begin(), box.end(), [](const vector<int> &a, const vector<int> &b) {
                return a[0] < b[0];
            });
            int size = box.size();
            vector<int> dp(size, 0); // dp保存当前节点在底部的最大高度
            dp[0] = box[0][2];
            int ret = dp[0];
            for (int i = 1; i < size; ++i) {
                int max_val = 0;
                for (int j = 0; j < i; ++j) {
                    if (IsValid(box[j], box[i])) {
                        max_val = max(max_val, dp[j]); 
                    }
                }
                dp[i] = max_val + box[i][2];
                ret = max(ret, dp[i]);
            }
            return ret;
        }
    
    
        bool IsValid(vector<int> &up, vector<int> &down) {
            return (down.at(0) > up.at(0) 
                    && down.at(1) > up.at(1) 
                    && down.at(2) > up.at(2));
        }
    };
    

    相关文章

      网友评论

          本文标题:每日一题之堆箱子

          本文链接:https://www.haomeiwen.com/subject/jgccwhtx.html