I'm trying to figure out how to solve this problem:
We have n ≥ 1 parallelepiped-shaped boxes, labeled as 0, 1,… n - 1; box i has width x [i], height y [i] and depth z [i] (strictly positive real values).
We want to insert as many boxes one inside the other, similar to a "matryoshka": box i can be contained in box j if the dimensions of box i are strictly smaller than the corresponding ones of box j, that is, if x [i] <x [j] and y [i] <y [j] and z [i] <z [j].
Implement an efficient algorithm to determine the maximum number of boxes that can be inserted into each other respecting the previous constraints. The boxes cannot be rotated. The program accepts a single parameter on the command line that represents the name of the input file, the content of which has the following structure:
n
x [0] y [0] z [0]
...
x [n-1] y [n-1] z [n-1]
The output must list the boxes that are part of the optimal solution, one box per line, starting with the outermost one; for each of them the dimensions must be reported (as per input file).
#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct box {
float x, y, z; //width x, height y, depth z
}Box;
int cmpfunc (const void *a, const void *b) {
Box *boxA = (Box *)a;
Box *boxB = (Box *)b;
return (boxA->x - boxB->x);
}
void maxBoxes (Box *box, int n) {
qsort (box, n, sizeof(Box), cmpfunc);
Box *max_boxes;
max_boxes = (Box*)malloc(n * sizeof(Box));
assert (max_boxes != NULL);
int n_boxes = 0;
for (int i=0; i<n; i++) {
for (int j=0; j < i; j++) {
if (box[i].x < box[j].x && box[i].y < box[j].y && box[i].z < box[j].z) {
max_boxes[i] = box[i];
n_boxes++;
}
}
}
printf ("%d boxes\n", n_boxes);
for (int i=0; i<n_boxes; i++) {
printf("Box %d: %.2f %.2f %.2f\n", i, max_boxes[i].x, max_boxes[i].y, max_boxes[i].z);
}
}
int main (int argc, char *argv[]) {
FILE *filein = stdin;
Box *box;
int n = 0;
if (argc > 1) {
filein = fopen(argv[1], "r");
if (filein == NULL) {
fprintf (stderr, "Can not open %s\n", argv[1]);
return EXIT_FAILURE;
}
}
fscanf (filein, "%d", &n);
if (n<=0) {
fprintf (stderr, "ERROR: arguments number equal to 0\n");
exit (EXIT_FAILURE);
}
box = (Box*)malloc(n * sizeof(Box));
assert (box != NULL);
for (int i=0; i<n; i++) {
fscanf (filein, "%f %f %f", &box[i].x, &box[i].y, &box[i].z);
}
maxBoxes (box, n);
fclose(filein);
}
I tried but my code returns me only "0 boxes" on the screen. I think I have some problems with the structs. I wanted to create an array of struct but I don't know if I did it right.
If you have some advice I'll be happy to listen to them.
You can solve the problem by topological sorting the boxes according to "contains" relation and use dynamic programming to track how long chain of boxes can be put into previous boxes. Start from the boxes that contains no other boxes. When you add a new box just iterate over boxes that fit to the given to find the one with the longest chain that fits to the current box.
Finally, reconstruct the chain starting from the box with the largest score. Complexity is O(N^2). Here's the code:
#include <stdio.h>
#include <stdlib.h>
int main() {
int n;
scanf("%d", &n);
struct box {
float x,y,z;
// the longest chain, 0 - score is undefined
int score;
// number of non-processes boxes that fits to this box
int deg;
int prev;
};
// allocate and load
struct box *B = calloc(n, sizeof *B);
for (int i = 0; i < n; ++i) {
scanf("%f %f %f", &B[i].x, &B[i].y, &B[i].z);
B[i].prev = -1;
}
#define CONTAINS(a,b) (a.x > b.x && a.y > b.y && a.z > b.z)
// compute number of boxes that fit to n-th box
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (CONTAINS(B[i], B[j]))
B[i].deg++;
for (;;) {
int i;
// find not processed box that
for (i = 0; i < n; ++i) {
if (B[i].deg == 0 && B[i].score == 0)
break;
}
// no boxes were found, quit
if (i == n) break;
// mark as processed, set score to 1, as box contains itself
B[i].score = 1;
// look for the box with the longest chain that fits to box `i`
for (int j = 0; j < n; ++j) {
if (CONTAINS(B[i], B[j]) && B[j].score + 1 > B[i].score) {
B[i].score = B[j].score + 1;
B[i].prev = j;
}
}
// reduce deg (number of unprocessed boxes that fits given box)
// for boxes that contains i-th box
for (int j = 0; j < n; ++j) {
if (CONTAINS(B[j], B[i]))
B[j].deg--;
}
}
// find the box with the best score
int best = 0;
for (int i = 0; i < n; ++i)
if (B[i].score > B[best].score)
best = i;
printf("%d boxes\n", B[best].score);
for (int i = best; i != -1; i = B[i].prev)
printf("box %d: %g %g %g\n", i, B[i].x, B[i].y, B[i].z);
free(B);
}
for input:
10
10 3 4
2 2 3
3 2.5 3
4.4 5 6
7 5.1 7.4
9 8.7 5.6
8.7 6.5 9.5
2.5 6.5 7.3
5.7 8.7 9.3
7.6 5.1 6.2
An expected output is produced:
4 boxes
box 6: 8.7 6.5 9.5
box 4: 7 5.1 7.4
box 3: 4.4 5 6
box 1: 2 2 3