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