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.
Code:
#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; }
No comments:
Post a Comment