0

I'm facing a problem described as follows:

You are given a set of $n$ types of rectangular 3-D boxes, where the i-th box has height, width, depth and profit. You want to create a stack of boxes with a height limit H(weight) and maximize the sum of the profit, but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each larger or equal than those of the 2-D base of the higher box. Of course, you can rotate a box so that any side functions as its base. You are also allowed to use multiple instances of the same type of boxes.

I realized that it is a combination of the unbounded knapsack problem and the box stacking problem with small variations. I tried to solve it using the unbounded knapsack algorithm adding the box stacking restrictions. It works when I use the recursive top-down approach (code available here). What I'm trying to do is to implement a top-down approach with memoization, since I have to return the value of the profit and also the picked items.

The professor told me I need to use a three-dimensional array in order to calculate the result of my problem, so I tried to implement it (code available here). But with the help provided in the comment section, I realized that I'm not able to run it on my machine. Is there any other way to store and retrieve the picked items?

The files ending with .data are instances of the problem, and they have the following format:

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

Here follows my code:

#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;
}
user2134
  • 1
  • 1
  • Is there a reason you can’t use C++? It’s much easier dealing with nested arrays as std::vector for example. Also, did you try using a debugger? Which line does crash? – deets Apr 28 '18 at 21:37
  • The code that frees the arrays seems a little off. Every `free` should match the corresponding `malloc`. The `malloc` loop uses `weight` and `depth`, but the `free` loop uses `depth` and `width`. – user3386109 Apr 28 '18 at 21:42
  • @deets it is a homework and it is mandatory to use c. I'm using a debugger but it didn't inform the line where it crashes. – user2134 Apr 28 '18 at 21:54
  • @user3386109 did you mean for (int i = 0; i<= weight; i++) for (int j = 0; j <= depth; j++) free(m[i][j]); for (int i = 0; i<= weight; i++) free(m[i]); free(m)? I'm still getting the sigkill signal – user2134 Apr 28 '18 at 22:00
  • 1
    You need to compile with -g as Compiler Argument to actually generate debugging information so the debugger can give you line info. – deets Apr 28 '18 at 22:12
  • Yup, that's what I meant. What are the maximum values for `weight`, `depth`, and `width`? – user3386109 Apr 28 '18 at 22:28
  • @user3386109 it depends on the instance, it could be 2349, 930, 930 for example – user2134 Apr 28 '18 at 23:00
  • 2
    So if an `int` is 4 bytes, then you're attempting allocate more than `2350*931*931*4` bytes (8GB). I hope your computer has a least 16GB of memory. Another possibility is that there's a per-process limit on memory usage. You would get a SIGKILL if you exceed the process memory limit. – user3386109 Apr 28 '18 at 23:05
  • But what could I use to replace the 3D array and not get the SIGKILL? – user2134 Apr 28 '18 at 23:16
  • 1
    "I need to use a three-dimensional array in order to calculate the result of my problem" --> maybe there is another, more memory efficient, approach that does not "SIGKILL". Describe the overall coding goal. for some ideas. – chux - Reinstate Monica Apr 29 '18 at 01:15
  • 1
    It's unlikely you're getting SIGKILL; you may well be getting a signal. You don't check that your memory allocations succeed — with big arrays, that becomes very important. You've shown some code, but you've not shown how it is used — it isn't an MCVE ([MCVE]). However, we also need to know about the sample data, especially for the version that crashes. I agree that you're probably allocating more space than you have available. I observe that your code doesn't show the `num_boxes` or `boxes` variables in use; they should be missing from an MCVE. (You do use version control, don't you?) – Jonathan Leffler Apr 29 '18 at 03:19
  • @chux, I provided more details about the problem. – user2134 Apr 30 '18 at 00:15
  • @JonathanLeffler, I don't use version control. – user2134 Apr 30 '18 at 00:18
  • @melpomene I'm running it on my windows machine and an online compiler at the same time. In my machine, it just stops working but the online compiler debugger gave me the SIGKILL signal. Should I remove the windows tag? – user2134 Apr 30 '18 at 00:49
  • 1
    no online compiler will give you 8GB of memory. And you [don't cast the result of malloc in C](https://stackoverflow.com/q/605845/995714) – phuclv Apr 30 '18 at 00:50
  • @LưuVĩnhPhúc, even my machine doesn`t have 8GB of memory, but this was the solution proposed by my professor. Now I know that the solution proposed it is impossible to run on my machine. What I'm looking now is another way to retrieve the picked items. I'll change my title and my question. – user2134 Apr 30 '18 at 01:07
  • I see no need for a full 3D array. You may want to use a [sparse 3D array](https://en.wikipedia.org/wiki/Sparse_matrix). Certainly this is what the professor meant. – chux - Reinstate Monica Apr 30 '18 at 12:16
  • If you don't use version control, you're making it hard for yourself to make changes. When something more or less works, or you just want to keep a record of what you've done up until now so you can make some changes that could be difficult, you need to save the current version of the code in a VCS. Then you can go back to a known state (any previous known state) when necessary. It is also relevant to making an MCVE; you make a copy of the code, and hack some material out of it, and check whether the code reproduces the problem. If it does, save the current code as a simpler version. – Jonathan Leffler May 01 '18 at 00:12
  • If it doesn't reproduce the problem, you hacked out too much code; go back to the previous reproducing version and start again. This is much, much simpler if you use a VCS. Which is why I asked whether you use a VCS. – Jonathan Leffler May 01 '18 at 00:14

0 Answers0