Algorithm
Problem link- https://www.spoj.com/problems/BABTWR/
BABTWR - Tower of Babylon
Apart from the Hanging Gardens the Babylonians (around 3000-539 b.c.) built the Tower of Babylon as well. The tower was meant to reach the sky, but the project failed because of a confusion of language imposed from much higher above.
For the 2638th anniversary a model of the tower will be rebuilt. n different types of blocks are available. 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 eachother 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.
Input
The number of types of blocks n is located in the first line of each test case. On the subsequent n lines the height yi, the width xi and the depth zi of each type of blocks are given. There are never more than 30 different types available.
There are many test cases, which come one by one. Input terminates with n = 0.
Edited: You can assume that max(xi, yi, zi) <= 2500.
Output
For each test case your program should output one line with the height of the highest possible tower.
Example
Sample input: 5 31 41 59 26 53 58 97 93 23 84 62 64 33 83 27 1 1 1 1 0 Sample output: 342 1
Code Examples
#1 Code Example with PHP Programming
Code -
C++ Programming
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <map>
#include <list>
using namespace std;
struct Box{
int h,w,d;
};
int compare(const void *a,const void *b){
return ( (*(Box *)b).d * (*(Box *)b).w ) -
( (*(Box *)a).d * (*(Box *)a).w );
}
int maxStackHeight(Box arr[],int n){
Box rot[6*n];
int index=0;
for(int i=0;i<n;i++){
rot[index]=arr[i];
index++;
rot[index].h=arr[i].w;
rot[index].w=arr[i].h;
rot[index].d=arr[i].d;
index++;
rot[index].h=arr[i].d;
rot[index].w=arr[i].w;
rot[index].d=arr[i].h;
index++;
rot[index].h=arr[i].d;
rot[index].w=arr[i].h;
rot[index].d=arr[i].w;
index++;
rot[index].h=arr[i].w;
rot[index].w=arr[i].d;
rot[index].d=arr[i].h;
index++;
rot[index].h=arr[i].h;
rot[index].w=arr[i].d;
rot[index].d=arr[i].w;
index++;
}
n=6*n;
qsort(rot,n,sizeof(rot[0]),compare);
int msh[n];
for (int i = 0; i < n; i++ )
msh[i] = rot[i].h;
for(int i=1;i<n;i++){
for(int j=0;j<i;j++){
if ( rot[i].w < rot[j].w &&
rot[i].d < rot[j].d &&
msh[i] < msh[j] + rot[i].h)
{
msh[i] = msh[j] + rot[i].h;
}
}
}
int max = -1;
for ( int i = 0; i < n; i++ )
if ( max < msh[i] )
max = msh[i];
return max;
}
int main(){
int n;
while(true){
scanf("%d",&n);
if(n==0)break;
Box arr[n];
for(int i=0;i<n;i++){
//int h,w,d;
scanf("%d%d%d",&arr[i].h,&arr[i].w,&arr[i].d);
}
printf("%d\n",maxStackHeight(arr,n));
}
return 0;
}
Copy The Code &
Try With Live Editor
Input
31 41 59
26 53 58
97 93 23
84 62 64
33 83 27
1
1 1 1
0
Output
1
Demonstration
SPOJ Solution-BABTWR Tower of Babylon- Solution in C, C++, Java, Python, SPOJ Solution,BABTWR