In my previous post I wrote about solving the Stacking Boxes problem using graphs. In this post I will write about a simpler method that utilizes dynamic programming that solves the same problem with half the amount of code.
I will assume you have read my previous post on using graphs, though you haven’t you can check it out here: 103 – Stacking Boxes (Graph Method) – UVa Tutorial. I will refer longest increasing subsequence as LIS and dynamic programming as dp.
- Link to solution source code (github.com)
- Solution run time: 0.000 (no different than graph solution)
- Language: C++11
On the O(n^2) LIS Dynamic Programming Solution
In using dynamic programming there are 2 variants of the algorithm: one solves in O(n^2) and another in O(n*log n), the later of which replaces the inner loop in the former algorithm with a binary search using an algorithm called Patience Sorting. I will be using the simpler, quadratic time variant. I won’t attempt to explain the algorithm in detail, but there are plenty of resources out there to help you wrap your head round it:
- Tushar Roy’s step by step of the algorithm (youtube video)
- Geeksforgeeks article
- Bo Qian’s youtube video (with C++ code)
- Article on Algorithmist (succinct, though can be tough to understand).
The first 2 resource will only find the length of the LIS, though that process is the heart of the algorithm. Once you can find that, getting the sequence itself is not that hard.
A Generic LIS Implementation
The code here is based off a stackoverflow answer.
template<typename T>
deque<T> find_lis(const vector<T> &a,
function<bool(const T &, const T &)> comp = [&](const T &a, const T &b)->bool { return a < b; })
{
int maxLength = 1, bestEnd = 0;
vector<int> DP(a.size(), 1);
vector<int> prev(a.size(), -1);
for (int i = 1; i < a.size(); i++) { for (int j = i - 1; j >= 0; j--) {
if (DP[j] + 1 > DP[i] && comp(a[j], a[i])) {
DP[i] = DP[j] + 1;
prev[i] = j;
}
}
if (DP[i] > maxLength) {
bestEnd = i;
maxLength = DP[i];
}
}
deque<T> lis;
for (int i = bestEnd; i != -1; i = prev[i]) {
lis.push_front(a[i]);
}
return lis;
}
Using the function itself is pretty straightforward. You pass a vector that contains your sequence and it spits out the LIS as a deque. Here’s a github gist that test drives this function. You also have an option to modify the comparator, which in the gist is used to change the LIS algorithm to find the longest decreasing subsequence.
Solution Explanation
Once you understood what the LIS algorithm is doing, the rest is pretty much a no brainer. Once you sort the boxes and its dimensions, you can find the LIS is about 5 lines of code:
auto comp = [&](const Box *a, const Box *b)->bool { return canFit(a, b); };
auto lis = find_lis<Box*>(boxes, comp);
cout << lis.size() << endl;
for (auto b : lis) cout << b->id << " ";
cout << endl;
The only thing you need to customize here is the comparator; you will get the LIS based on whether the boxes will fit into each other. I handle this will a simple lambda function comp which I input inside find_lis. The canFit function is the exact same function in the graph method solution.
Bruceoutdoors Blog of Blots 