Можно ли решить проблему трехмерного ранца с помощью динамического программирования?

Question

Я пытался решить проблему рюкзака в 3d (ширина, высота, глубина, а не только вес), но, похоже, он не нашел правильного решения.

Проблема: Учитывая прямоугольник пространстваи прямоугольник, сколько ящиков можно уместить в пространстве?Коробка может быть в любом вращении, и их количество не ограничено.

Вот что я пробовал:

По сути, это таблица 4d, где i, x, y,Позиция z в таблице представляет потенциальный объем (x, y, z), который может быть заполнен элементами.Я только что расширил решение по динамическому программированию 1d рюкзака.

// c#
public static int Solve(Rectangle space, Rectangle box) {

    Rectangle[] boxes = createPermutations(box);
    int[,,,] table = new int[boxes.Length, space.width + 1, space.height + 1, space.depth + 1];

    for (int i = 0; i < boxes.Length; i++) {
        var curBox = boxes[i];
        var curBoxVolume = curBox.GetVolume();

        for (int x = 0; x < table.GetLength(1); x++) {
            for (int y = 0; y < table.GetLength(2); y++) {
                for (int z = 0; z < table.GetLength(3); z++) {

                    // Get the default value, if no box can be added.
                    int val = Mathf.Max(0, 
                        GetValue(table, i-1, x, y, z),
                        GetValue(table, i, x-1, y, z),
                        GetValue(table, i, x, y-1, z),
                        GetValue(table, i, x, y, z-1));

                    // Calculate the positions of the values to include
                    int xRem = x - curBox.width;
                    int yRem = y - curBox.height;
                    int zRem = z - curBox.depth;

                    // If a new box fits
                    if (xRem >= 0 && yRem >= 0 && zRem >= 0) {

                        // Get the new value
                        val = curBoxVolume + GetValue(table, i, xRem, y, z) + GetValue(table, i, x, yRem, z) + GetValue(table, i, x, y, zRem)
                            - GetValue(table, i, xRem, yRem, z) - GetValue(table, i, xRem, y, zRem) - GetValue(table, i, x, yRem, zRem)
                            + GetValue(table, i, xRem, yRem, zRem);
                    }

                    table[i, x, y, z] = val;
                }
            }
        }
    }

    return GetValue(table, boxes.Length - 1, space.width, space.height, space.depth);
}

public static Rectangle[] createPermutations(Rectangle box) {
    // All possible rotations of the single box
    List<Rectangle> rects = new List<Rectangle>() {
        box, // 1,2,3
        box.GetPermutation(1,3,2),
        box.GetPermutation(2,1,3),
        box.GetPermutation(2,3,1),
        box.GetPermutation(3,1,2),
        box.GetPermutation(3,2,1)
    };
    return rects.Distinct(new Rectangle(0, 0, 0)).ToArray();
}

public static int GetValue(int[,,,] table, int i, int x, int y, int z) {
    if (x < 0 || y < 0 || z < 0 || i < 0 || 
        i >= table.GetLength(0) || x >= table.GetLength(1) || y >= table.GetLength(2) || z >= table.GetLength(3)) {
        return 0;
    }
    return table[i, x, y, z];
}

Вычисление значения (val) кажется немного странным, вот как я его разработал.Может быть, именно в этом моя проблема, я не уверен.

С пробелом: 2,2,2, поле: 1,1,1, ответ должен быть 8 (использованный объем и используемые ящики).Последнее значение рассчитывается по формуле: 4 + 4 + 4 - 2 - 2 + 1 + 1 (объем коробки). Это изображение демонстрирует это довольно хорошо, я думаю:

Я пытался использовать эту программу, чтобы проверить свои результаты с фактическим результатом: https://www.3dbinpacking.com/en/products/fill-container

Вот пример, где мое решение неверно

    Rectangle space = new Rectangle(4, 8, 10);
    Rectangle box = new Rectangle(2, 3, 2);
    int result = Packing3d.Solve(space, box);

Решение выходитзаполнено только на 75%, но результат веб-сайта составляет 97,5%

Стоит отметить, что мое решение работает, когда проблема двумерная.