结构数组有问题解决C中的问题

Question

我正在想办法解决这个问题：

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);
}

我试过了，但我的代码 returns 屏幕上只有“0 个框”。我想我的结构有一些问题。我想创建一个结构数组，但我不知道我做对了没有。

如果你有什么建议，我很乐意听取。

Answer 1

您可以通过根据“包含”关系对盒子进行拓扑排序来解决问题，并使用动态规划来跟踪可以将多长的盒子链放入先前的盒子中。从不包含其他框的框开始。当您添加一个新框时，只需遍历适合给定框的框，以找到具有适合当前框的最长链的框。

最后，从分数最大的盒子开始重构链。复杂度为 O(N^2)。这是代码：

#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);
}

输入：

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

产生了预期的输出：

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

结构数组有问题解决C中的问题

Having problem with array of struct solving a problem in C

c

struct

arguments

quicksort