CareerCup

With 3 dimensions it should not be a problem. Expanding this to K dimensions. You would work on all of those for the constraint, but for the height you would need to know which one is the height.

You need to consider that someone could turn the box and therefore change the height. In that case, you would need to expand the search so you can use any dimension as height. If so, you could always place the height on the same location inside the Box object.

So, you could for each box, turn and see if this new box can create the max stack... You could come up with a method that given a box, it will output a list of "new boxes" which are the turns for the first one. All those new boxes would be part of the box list and then you would use the same algorithm with the caveat of making sure that you are not putting the same box on top of itself and having the height always in the same place.

def max_stack(boxes, bottom, cache, in_use):
    if boxes is None or cache is None: raise

    if bottom is not None and cache.has_key(bottom):
        return cache[bottom]
             
    max_st = []
    for i in range(len(boxes)):
        box = boxes[i]
        if box.is_allowed_above(bottom) and not in_use[i]:
            in_use[i] = True

            # Rotates for all dimensions (They all can be the height)
            rotations = box.create_rotations() 
            for box_rotation in rotations:
                max_sub = max_stack(boxes, box_rotation, cache, in_use)

                # Since we have all possible rotations, we can assume that
                # the height will always be placed on the same index (if we have
                # an array as dimensions)
                if calculate_height(max_sub) > calculate_height(max_st):
                    max_st = []
                    max_st.extend(max_sub)

            in_use[i] = False

    if bottom is not None:
        max_st.append(bottom)

    cache[bottom] = max_st
    return max_st

This problem is one of the problems in Cracking the Code Interview. Check out the Dynamic Programming chapter. The idea is that for every box, you will find the biggest stack that can be put on top of that box. The biggest stack for the current box is now the biggest stack you can put on top of it with the box itself as the bottom box. Just be careful when you get boxes with the same size. Unless you consider those "the same box", you will need to, maybe, mark boxes as used. Here is a simple code to give you some direction.

def max_stack(boxes, bottom, cache):
    if boxes is None or cache is None: raise

    if bottom is not None and cache.has_key(bottom):
        return cache[bottom]
             
    max_st = []
    for box in boxes:
        if box.is_allowed_above(bottom):           
            max_sub = max_stack(boxes, box, cache)
            if calculate_height(max_sub) > calculate_height(max_st):
                max_st = []
                max_st.extend(max_sub)

    if bottom is not None:
        max_st.append(bottom)

    cache[bottom] = max_st
    return max_st

Following are three solutions:
1. A simple recursive solution for the box stacking problem in 3 dimensions.
2. A dynamic programming solution for the box stacking problem in 3 dimensions.
3. A dynamic programming solution for the box stacking problem in K dimensions.

Solution 1:

class Box {
public: 
    int h, w, l;
    Box(int _h, int _w, int _l) : h(_h), w(_w), l(_l) {};
};

int msha(const std::vector<Box>& boxes, int ch, int bh, int bw)
{
    auto max = ch;
    for (const auto& b : boxes)
    {
        if ((b.h < bh && b.w < bw) || (b.w < bh && b.h < bw))
        {
            max = std::max(max, msha(boxes, ch + b.l, b.h, b.w));
        }
        if ((b.h < bh && b.l < bw) || (b.l < bh && b.h < bw))
        {
            max = std::max(max, msha(boxes, ch + b.w, b.h, b.l));
        }
        if ((b.l < bh && b.w < bw) || (b.w < bh && b.l < bw))
        {
            max = std::max(max, msha(boxes, ch + b.h, b.l, b.w));
        }
    }
    return max;
}

int msh(const std::vector<Box>& boxes)
{
    return msha(boxes, 0, std::numeric_limits<int>::max(), std::numeric_limits<int>::max());
}

Solution 2:

class Box {
public: 
    int h, w, l;
    Box(int _h, int _w, int _l) : h(_h), w(_w), l(_l) {};
};

void get_dims(const Box& b, int type, int& h, int &w, int& l)
{
    if (0 == type)
    {
        h = b.h; w = b.w; l = b.l;
    }
    else if (1 == type)
    {
        h = b.l; w = b.w; l = b.h;
    }
    else if (2 == type)
    {
        h = b.h; w = b.l; l = b.w;
    }
}

int msh_dp(const std::vector<Box>& boxes)
{
    auto n = boxes.size() * 3;
    auto d = new int[n];
    for (auto i = 0; i < n; ++i)
    {
        auto h = 0, w = 0, l = 0;
        get_dims(boxes[i / 3], i % 3, h, w, l);
        d[i] = l;
    }

    for (auto k = 0; k < 4; ++k)
    { 
        for (auto i = 0; i < n; ++i)
        {
            auto hi = 0, wi = 0, li = 0;
            get_dims(boxes[i / 3], i % 3, hi, wi, li);
            for (auto j = 0; j < n; ++j)
            {
                auto hj = 0, wj = 0, lj = 0;
                get_dims(boxes[j / 3], j % 3, hj, wj, lj);
                if ((hi < hj && wi < wj) || (hi < wj && wi < hj))
                {
                    d[i] = std::max(d[i], d[j] + li);
                }
            }
        }
    }

    auto max = 0;
    for (auto i = 0; i < n; ++i)
    {
        max = std::max(max, d[i]);
    }

    delete[] d;
    return max;
}

Solution 3:

namespace BoxStacking {

    template <size_t K = 3>
    class Box 
    {
    public:

        std::vector<int> dims;
        Box(std::initializer_list<int> _dims) 
        {
            if (_dims.size() != K) throw std::invalid_argument((boost::format("Box<%1%>() invalid number of dimensions") % K).str());
            dims = _dims;
        }
    };

    void get_perms_aux(std::vector<int>& v, std::list<std::vector<int>>& p, int k, int n)
    {
        if (k == n) 
        { 
            p.push_back(v);
            return;
        }
        for (auto i = k; i < n; ++i)
        {
            std::swap(v[k], v[i]);
            get_perms_aux(v, p, k+1, n);
            std::swap(v[k], v[i]);
        }
    }

    void get_perms(const std::vector<int>& v, std::list<std::vector<int>>& p)
    {
        std::vector<int> v2(v);
        get_perms_aux(v2, p, 0, v2.size());
    }

    template <size_t K>
    int msh_dp(const std::vector<Box<K>>& boxes)
    {
        auto n = boxes.size() * K;
        auto d = new int[n];
        for (auto i = 0; i < n; ++i)
        {
            d[i] = boxes[i / K].dims[i % K];
        }

        // repeat 4 times because every box could be selected at most twice so the number of possible stackings is (2n)^2 = 4*n^2
        for (auto l = 0; l < 4; ++l) 
        {
            for (auto i = 0; i < n; ++i)
            {
                auto idims = boxes[i / K].dims;
                auto height_value = idims[i % K];
                idims.erase(std::begin(idims) + (i % K));
                std::list<std::vector<int>> perms;
                get_perms(idims, perms);
                for (auto j = 0; j < n; ++j)
                {
                    auto jdims = boxes[j / K].dims;
                    jdims.erase(std::begin(jdims) + (j % K));
                    for (const auto& p : perms)
                    {
                        auto fits = true;
                        auto m = jdims.begin();
                        auto n = p.begin();
                        for (; n != p.end(); ++m, ++n)
                        {
                            if (*m <= *n)
                            {
                                fits = false;
                                break;
                            }
                        }
                        if (fits)
                        {
                            d[i] = std::max(d[i], d[j] + height_value);
                        }
                    }
                }
            }
        }

        auto max = 0;
        for (auto i = 0; i < n; ++i) max = std::max(max, d[i]);
        delete[] d;
        return max;
        
    }


    void test_msh_dp()
    {
        std::vector<Box<4>> boxes;
        boxes.push_back({ 2, 2, 2, 2 });
        boxes.push_back({ 4, 4, 4, 4 });
        boxes.push_back({ 8, 6, 4, 2 });
        auto msh = msh_dp(boxes);
        boxes.push_back({ 7, 5, 3, 1 });
        msh = msh_dp(boxes);
    }

};

Note that the generalized solution for K dimensions has a run time complexity of O(n^2*K!) and a space complexity of O(n*K + K!). This is because all permutations of the dimensions have to be checked for a fit (in 3 dimensions there are only 6 permutation tested for each box). Also note that a box may be selected in the stack at most twice which is the reason for the 4 repetitions in the outer loop in both dynamic programming solutions.