CODEWITHSUNDEEP
algorithmdynamic-programming
John Mòf
John Mòf

Reputation: 115

Dynamic programming: box stacking variation

We have n boxes whose dimensions are x, y, z (width, height, depth). We want to insert the largest number of boxes one inside the other.
You can put a box inside the other if the size of the inner box (i) are strictly less than the size of the outer box (j): x[i] < x[j], y[i] < y[j], z[i] < z[j].
The boxes CAN'T be rotated and can be considered in any order.

How can I achieve the goal with the dynamic programming?
The issue is similar to the longest increasing subsequence problem?
It can make sense to order boxes in ascending / descending order?

Upvotes: 4

Views: 1430

Answers (2)

Novak
Novak

Reputation: 4779

Perform a topological sort on the boxes, arranging them into a graph as follows: Each box is a node in a graph, each directed arc from node A to node B indicates that the corresponding Box A holds Box B. Augment this structure with a box of infinite size and a box a zero size.

As a topological sort, this graph will be a directed acyclic graph. As such, finding the longest path is not NP-hard, but rather can be solved in O(V+E). The longest path between your two augmenting boxes contains the answer to the problem.

Setting up the sort is O(V^2), and finding the solution from the sorted graph is O(V+E) which in this context is O(V^2) which is your overall solution time.

Upvotes: 4

Vaughn Cato
Vaughn Cato

Reputation: 64308

Here is a simple top-down approach in C++:

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using std::cin;
using std::cout;
using std::vector;
using std::ostream;

// G[i][j]==true if box i will fit inside box j.
// L[i] is the number of boxes that will fit inside box i, or -1 if
//      this value has not been determined.

// Calculate how many boxes will fit inside box j.
static int count(const vector<vector<bool>> &G,vector<int> &L,int j)
{
    int n = L.size();
    int max_x = 0;

    for (int i=0; i!=n; ++i) {
        if (G[i][j]) {
            if (L[i]==-1) {
                L[i] = count(G,L,i);
            }
            int x = L[i]+1;
            if (x>max_x) {
                max_x = x;
            }
        }
    }

    return max_x;
}


int main()
{
    int n; cin >> n;
    vector<int> x(n+1), y(n+1), z(n+1);

    for (int i=0; i!=n; ++i) {
        cin >> x[i] >> y[i] >> z[i];
    }

    // Add a huge box that contains any box
    x[n] = INT_MAX;
    y[n] = INT_MAX;
    z[n] = INT_MAX;

    vector<vector<bool> > G(n+1,vector<bool>(n+1,false));

    for (int i=0; i!=n+1; ++i) {
        for (int j=0; j!=n+1; ++j) {
            G[i][j] = x[i]<x[j] && y[i]<y[j] && z[i]<z[j];
        }
    }

    vector<int> L(n,-1);

    // Print the number of boxes that will fit in the huge box.
    cout << count(G,L,n) << "\n";
}

There are various ways to make this faster, but this shows the recursive formulation which allows the use of dynamic programming.

Upvotes: 0

Related Questions