Problem
Given n different types of blocks. Each one of them may be duplicated as many times as you like. Each type has a height y, a width x and a depth z. The blocks are to be stacked one upon each other so that the resulting tower is as high as possible. Of course the blocks can be rotated as desired before stacking. However for reasons of stability a block can only be stacked upon another if both of its baselines are shorter.
Example
Sample input: 5 31 41 59 26 53 58 97 93 23 84 62 64 33 83 27
Sample output: 342
Tower of Babylon Solution
Approach
This problem is similar to finding the longest increasing subsequence (LIS).
Let’s consider all the rotations of a block and add it to an array of structure of block [Block]. Block is a data structure with three integer variables x, y, and z.
Since we need the tallest tower, we sort all the blocks in an increasing order of their dimensions by x, y and then z.
Optimal Substructure
After that we traverse block array and find the optimum solution, where optimum solution is maximum of the following:
- Tallest tower obtained by n-1 elements, excluding nth element.
- nth element + tallest tower obtained by n-1 elements
Then, LIS(i) [Longest Increasing Sequence] can be recursively written as:
// 'z' is the z or height dimension of the block if LIS[i] < LIS[j] + block[i].z LIS(i) = block[i].z + LIS[j] where 0 < j < i; else LIS(i) = 1, if no such j exists. ans = MAX(ans, LIS[i])
Code Implementation
//
// main.cpp
// Tower of Babylon
//
// Created by Himanshu on 17/09/21.
//
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
struct block {
int x,y,z;
};
bool cmp(const struct block &a,const struct block &b) {
if(a.x != b.x)
return (a.x < b.x);
else if(a.y != b.y)
return (a.y < b.y);
else
return (a.z < b.z);
}
block newBlock(int p,int q,int r) {
block b;
b.x = p;
b.y = q;
b.z = r;
return b;
}
int main() {
int n, ans, p, q, r;
scanf("%d",&n);
// Since each block can be rotated in 6 ways, 1 for each face
int N = 6*n;
block b[N];
int lis[N];
// Input terminates for n = 0, according to problem statement
while(n != 0) {
int j = 0;
ans = 0;
for(int i=0; i<n; i++) {
scanf("%d %d %d",&p,&q,&r);
// Adding all the combinations obtained by rotating a cuboid
b[j++] = newBlock(p,q,r);
b[j++] = newBlock(q,r,p);
b[j++] = newBlock(r,p,q);
b[j++] = newBlock(q,p,r);
b[j++] = newBlock(r,q,p);
b[j++] = newBlock(p,r,q);
}
sort(b,b+N,&cmp);
for(int i=0;i<N;i++) {
lis[i] = b[i].z;
for(j=0;j<i;j++) {
// To check if jth block can be placed above ith block
if((b[j].x < b[i].x && b[j].y < b[i].y) ||
(b[j].x < b[i].y && b[j].y < b[i].x)) {
//Optimal solution by including b[i] or not
lis[i] = max(lis[i],(lis[j]+b[i].z));
}
}
ans = max(ans,lis[i]);
}
printf("%d\n",ans);
scanf("%d",&n);
}
return 0;
}
Here’s a working example: Ideone