Given a lot of cuboid boxes with different length, breadth and height. We need to find the maximum subset which can fit into each other. For example: If Box 1 has LBH as 7 8 9 If Box 2 has LBH as 5 6 8 If Box 3 has LBH as 5 8 7 If Box 4 has LBH as 4 4 4 then answer is 1,2,4 A box can fit into another only and only if all dimensions of that is less than the bigger box.Rotation of boxes is not possible.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


/*Struct defining cube*/
typedef struct
{
int l;
int b;
int h;
}Cube;

/*Cube compare function */
int cube_compare(const void *x, const void *y)
{
const Cube *a = x;
const Cube *b = y;

if(a->l == b->l)
{
if(a->b == b->b)
return a->h - b->h;

return a->b - b->b;
}
return a->l - b->l;

}

/*Struct to hold successor info*/
typedef struct
{
int next;
int chainLength;
}Successor;


/*Checks whether cube 'a' fits into cube 'b' */
inline int cube_fits(Cube *a , Cube *b)
{
return (a->l < b-> l) && (a->b < b->b) && (a->h < b->h);
}

/*Prints all the cubes which fits into one another */
void max_fit_cubes(Cube cubes[], int n)
{

//Fill the chain
Successor nextCube[n];

memset(nextCube, 0, sizeof(nextCube));

int i = n - 1, j;

while(i--)
{
for(j = i + 1; j < n; j++)
{
if(cube_fits(cubes + i, cubes + j))
{
if((nextCube[j].chainLength + 1) > nextCube[i].chainLength)
{
nextCube[i].chainLength = nextCube[j].chainLength + 1;
nextCube[i].next = j;
}
}
}
}

//find the max chain
int m = i = n - 1;

while(i--)
{
if(nextCube[i].chainLength > nextCube[m].chainLength)
m = i;
}


//Now print the max chain

printf("Max Chain Length: %d, m: %d\n", nextCube[m].chainLength, m);

do
{
printf("(%d,%d,%d) =>", cubes[m].l, cubes[m].b, cubes[m].h);
m = nextCube[m].next;
}while(m);

printf("\n");
}

int main()
{
int n;

scanf("%d", &n);

Cube cubes[n];

int i;

for(i = 0; i < n; ++i)
{
scanf("%d%d%d", &(cubes[i].l), &(cubes[i].b), &(cubes[i].h));
}

qsort(cubes, n, sizeof(Cube), cube_compare);

max_fit_cubes(cubes, n);
return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s