Как извлечь выбранные предметы из неограниченного ранца, используя подход сверху вниз

Question

Я столкнулся с проблемой, описанной следующим образом:

Вам предоставляется набор из $ n $ типов прямоугольных трехмерных блоков, где У i-го ящика есть высота, ширина, глубина и прибыль. Вы хотите создать стопка ящиков с ограничением по высоте H (вес) и максимизации суммы прибыль, но вы можете сложить ящик только над другим, если размеры двухмерного основания нижней коробки больше или равны чем те из 2-ой основы более высокой коробки. Конечно вы можете поверните коробку так, чтобы любая сторона функционировала как ее основа. Вы также разрешено использовать несколько экземпляров ящиков одного типа.

Я понял, что это комбинация проблемы неограниченного ранца и проблемы укладки коробки с небольшими вариациями. Я попытался решить ее, используя алгоритм неограниченного ранца, добавив ограничения на укладку ящиков. Это работает, когда я использую рекурсивный нисходящий подход (код доступен здесь ). То, что я пытаюсь сделать, - это реализовать нисходящий подход с запоминанием, поскольку мне нужно возвращать значение прибыли, а также выбранных предметов.

Профессор сказал мне, что мне нужно использовать трехмерный массив для вычисления результата моей задачи, поэтому я попытался реализовать его (код доступен здесь ). Но с помощью, предоставленной в разделе комментариев, я понял, что не могу запустить его на своей машине. Есть ли другой способ хранения и извлечения выбранных предметов?

Файлы, заканчивающиеся на .data, являются экземплярами проблемы и имеют следующий формат:

num_boxes

max_height(weight)

profit_1

...

profit_num_boxes

width_1

height_1

depth_1

...

width_num_boxes

height_num_boxes

depth_num_boxes

Вот мой код:

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

int max_height;
int num_boxes;
int max_dimension;

typedef struct box {
    int height, width, depth, profit, rotations;
} Box;

int max(int x, int y) {
    return (x > y) ? x : y;
}

Box* readboxes(char* file) {

    FILE *in;
    int i = 0;
    int j = 0;
    int k = 0;
    int l = 0;
    int value;
    Box *boxes;

    in = fopen(file, "r");

    if (in == NULL)
        printf("Couldn't open the file\n");
    else {
        max_dimension = 0;
        if ((fscanf(in, "%d", &value)) != EOF) {
            num_boxes = value;
            i++;
        }
        boxes = malloc(sizeof(Box) * 2 * num_boxes);

        while ((fscanf(in, "%d", &value)) != EOF) {

            if (i == 1)
                max_height = value;
            if (i >= 2 && i < num_boxes + 2) {
                boxes[j].profit = value;
                j++;
            }
            if (i >= num_boxes + 2) {
                if (k % 3 == 0) {
                    max_dimension = max(max_dimension, value);
                    boxes[l].width = value;
                }

                if (k % 3 == 1) {
                    max_dimension = max(max_dimension, value);
                    boxes[l].height = value;
                }

                if (k % 3 == 2) {
                    max_dimension = max(max_dimension, value);
                    boxes[l].depth = value;
                }

                boxes[l].rotations = 1;
                k++;
                if (k % 3 == 0)
                    l++;
            }
            i++;
        }
    }
    return boxes;
}

void generateRotations(int num_boxes, Box *boxes) {
    int index = num_boxes;
    for (int i = 0; i < num_boxes; i++) {
        boxes[index].height = boxes[i].width;
        boxes[index].depth = boxes[i].depth;
        boxes[index].width = boxes[i].height;
        boxes[index].profit = boxes[i].profit;
        boxes[index].rotations = 2;
        index++;
    }
}

int compare(const void *a, const void * b) {
    return ((*(Box *) b).depth * (*(Box *) b).width)
            - ((*(Box *) a).depth * (*(Box *) a).width);
}

int*** create3DArray() {
    int *** m = malloc((max_height + 1) * sizeof(int**));
    for (int i = 0; i < (max_height + 1); i++) {
        m[i] = malloc((max_dimension + 1) * sizeof(int *));
        for (int j = 0; j < (max_dimension + 1); j++)
            m[i][j] = malloc((max_dimension + 1) * sizeof(int));
    }

    for (int i = 0; i <= max_height; i++)
        for (int j = 0; j <= max_dimension; j++)
            for (int k = 0; k <= max_dimension; k++)
                m[i][j][k] = -1;

    return m;
}

void free3DArray(int ***m) {

    for (int i = 0; i <= max_height; i++)
        for (int j = 0; j <= max_dimension; j++)
            free(m[i][j]);

    for (int i = 0; i <= max_dimension; i++)
        free(m[i]);

    free(m);

}
//need help here
int knapsack(int weight, int depth, int width, Box *boxes, int ***m) {

    int result_aux;
    int weight_aux;
    int depth_aux;
    int width_aux;

    if (m[weight][depth][width] != -1) {
        return m[weight][depth][width];
    }

    else {
        m[weight][depth][width] = 0;
        for (int i = 0; i < num_boxes; i++) {
            weight_aux = weight - boxes[i].height;
            depth_aux = boxes[i].depth;
            width_aux = boxes[i].width;
            if (weight_aux >= 0) {
                if (depth_aux <= depth && width_aux <= width) {
                    result_aux = knapsack(weight_aux, depth_aux, width_aux,
                            boxes, m) + boxes[i].profit;
                    if (result_aux > m[weight][depth][width])
                        m[weight][depth][width] = result_aux;
                }
            }
        }
    }

    return m[weight][depth][width];
}

int main(int argc, char *argv[]) {

    if (argc != 2) {
        printf("Arguments: \"in\" ");
    } else {
        Box *boxes = readboxes(argv[1]);

        generateRotations(num_boxes, boxes);
        num_boxes = 2 * num_boxes;

        qsort(boxes, num_boxes, sizeof(boxes[0]), compare);

        int ***m = create3DArray();

        printf("Profit: %d\n",
                knapsack(max_height, max_dimension, max_dimension, boxes, m));
        printf("Number of boxes: %d\n", num_boxes / 2);
        printf("Max height: %d\n", max_height);

        free(boxes);
        free3DArray(m);

    }

    return 0;
}