Skip to content

Instantly share code, notes, and snippets.

@ivycheung1208
Last active August 29, 2015 14:05
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ivycheung1208/9b0c648aacdb1d52ae11 to your computer and use it in GitHub Desktop.
Save ivycheung1208/9b0c648aacdb1d52ae11 to your computer and use it in GitHub Desktop.
CC150 9.10
/* CC150 9.10 */
// stack of boxes
#include <iostream>
#include <vector>
using namespace std;
class Box {
public:
Box() : width(0), height(0), depth(0) {}
Box(int w, int h, int d) : width(w), height(h), depth(d) {}
int getWidth() { return width; }
int getHeight() { return height; }
int getDepth() { return depth; }
bool isSmallerThan(Box box2) { // strictly smaller
return width < box2.getWidth() && height < box2.getHeight() && depth < box2.getDepth();
}
private:
int width, height, depth;
};
// Recursion (DP)
int maxHeight(vector<Box> boxes, int index, vector<int> &heights) // find tallest stack with bottom 'index'
{
if (index != -1 && heights[index] != 0)
return heights[index];
int hmax = 0;
for (int i = 0; i != boxes.size(); ++i) {
if (index == -1 || boxes[i].isSmallerThan(boxes[index])) { // box i can be placed here
int h = maxHeight(boxes, i, heights);
if (h > hmax) hmax = h;
}
}
if (index == -1) // no bottom box, return hmax directly
return hmax;
else { // bottom box is index, add its heights to hmax
heights[index] = hmax + boxes[index].getHeight();
return heights[index];
}
}
int maxHeight(vector<Box> boxes)
{
if (boxes.empty())
return 0;
vector<int> heights(boxes.size(), 0);
return maxHeight(boxes, -1, heights); // index = -1 indicating no box is placed as bottom yet
}
int main()
{
int n;
cout << "Number of boxes: ";
cin >> n;
vector<Box> boxes;
int width, height, depth;
cout << "Widths, heights, and depths of the boxes: " << endl;
for (int i = 0; i != n; ++i) {
cin >> width >> height >> depth;
boxes.push_back(Box(width, height, depth));
}
cout << "Height of the tallest stack: " << maxHeight(boxes) << endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment