如何通过回溯法实现2D货车的包裹装载功能？技术咨询

现有一辆需为客户配送包裹的货车，其存储区域为2D平面，宽度800cm、长度370cm，需从后往前装载包裹（不考虑高度）。已定义如下Java代码，咨询如何通过回溯法实现fillVan方法，是否可通过扣除尺寸的方式处理包裹装载？

public class Van {

    public Van() {
        Dimension2D storage = new Dimension2D(800, 370);
    }

    // TODO: how the hell do I fill the van with backtracking
    public void fillVan(ArrayList<Package> packages) {
        
    }

1. 回溯法核心思路 #

回溯法的核心是尝试-回退：遍历所有未装载的包裹，尝试将其放入当前可用的存储区域；若放置成功则递归处理剩余包裹，若后续无法完成装载或当前包裹无法放置，则回退状态，尝试下一个包裹。这种方式能穷举所有可行的装载组合，最终筛选出最优方案。

2. 扣除尺寸的方式是否可行？ #

完全可行。我们可以维护当前剩余的可用存储区域（初始为800x370），每次放置包裹后，根据包裹的摆放方向（横放/竖放）扣除对应尺寸，并将剩余区域拆分为1-2个新的可用矩形区域（比如包裹右侧的窄条、包裹前方的大矩形）。结合从后往前装载的要求，只需以货车尾部为原点规划坐标，优先填充靠近尾部的区域即可。

3. 具体代码实现示例 #

先补充Package和Dimension2D的基础属性，再实现回溯逻辑：

import java.util.ArrayList;
import java.util.List;

public class Van {
    private Dimension2D storage;
    private List<Package> loadedPackages = new ArrayList<>();
    private List<Package> bestLoaded = new ArrayList<>();

    public Van() {
        this.storage = new Dimension2D(800, 370);
    }

    public void fillVan(ArrayList<Package> packages) {
        // 剪枝优化：按包裹面积降序排序，优先尝试大包裹，减少递归次数
        packages.sort((p1, p2) -> Integer.compare(p2.getWidth() * p2.getHeight(), p1.getWidth() * p1.getHeight()));
        backtrack(packages, 0, new ArrayList<>(), storage);
        this.loadedPackages = bestLoaded;
    }

    /**
     * 回溯递归方法
     * @param packages 所有待装包裹
     * @param index 当前尝试的包裹索引
     * @param currentLoaded 当前已装载的包裹
     * @param remainingSpace 当前剩余的可用存储区域
     */
    private void backtrack(ArrayList<Package> packages, int index, List<Package> currentLoaded, Dimension2D remainingSpace) {
        // 更新最优方案：记录装载数量最多的组合
        if (currentLoaded.size() > bestLoaded.size()) {
            bestLoaded = new ArrayList<>(currentLoaded);
        }

        for (int i = index; i < packages.size(); i++) {
            Package pkg = packages.get(i);
            if (pkg.isLoaded()) continue;

            // 尝试两种摆放方向：原方向、旋转90度
            int[] possibleWidths = {pkg.getWidth(), pkg.getHeight()};
            int[] possibleHeights = {pkg.getHeight(), pkg.getWidth()};

            for (int dir = 0; dir < 2; dir++) {
                int pkgW = possibleWidths[dir];
                int pkgH = possibleHeights[dir];

                // 检查是否能放入当前剩余区域
                if (pkgW <= remainingSpace.getWidth() && pkgH <= remainingSpace.getHeight()) {
                    // 标记包裹状态并记录位置（从后往前装载，以尾部为原点计算坐标）
                    pkg.setLoaded(true);
                    pkg.setPosition(
                        storage.getWidth() - remainingSpace.getWidth(),
                        storage.getHeight() - remainingSpace.getHeight()
                    );
                    currentLoaded.add(pkg);

                    // 拆分剩余空间：放置包裹后产生两个新的可用区域
                    Dimension2D rightSpace = new Dimension2D(remainingSpace.getWidth() - pkgW, pkgH);
                    Dimension2D frontSpace = new Dimension2D(remainingSpace.getWidth(), remainingSpace.getHeight() - pkgH);

                    // 递归处理剩余包裹，分别尝试填充两个剩余区域
                    backtrack(packages, i + 1, currentLoaded, rightSpace);
                    backtrack(packages, i + 1, currentLoaded, frontSpace);

                    // 回退操作：取消装载标记，移除当前包裹
                    pkg.setLoaded(false);
                    pkg.setPosition(-1, -1);
                    currentLoaded.remove(currentLoaded.size() - 1);
                }
            }
        }
    }

    // 辅助类：Dimension2D实现
    static class Dimension2D {
        private int width;
        private int height;

        public Dimension2D(int width, int height) {
            this.width = width;
            this.height = height;
        }

        public int getWidth() {
            return width;
        }

        public int getHeight() {
            return height;
        }
    }

    // 辅助类：Package实现
    static class Package {
        private int width;
        private int height;
        private boolean loaded;
        private int x;
        private int y;

        public Package(int width, int height) {
            this.width = width;
            this.height = height;
            this.loaded = false;
            this.x = -1;
            this.y = -1;
        }

        public int getWidth() {
            return width;
        }

        public int getHeight() {
            return height;
        }

        public boolean isLoaded() {
            return loaded;
        }

        public void setLoaded(boolean loaded) {
            this.loaded = loaded;
        }

        public void setPosition(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

关键细节说明 #

• 剪枝优化：按包裹面积降序排序，优先尝试大包裹，能快速找到较优方案，减少无效递归次数
• 多方向尝试：每个包裹尝试横放、竖放两种姿态，提升空间利用率
• 剩余空间拆分：放置包裹后拆分出两个可用区域，确保后续递归能覆盖所有剩余空间
• 从后往前装载：通过坐标计算实现，以货车尾部为原点，优先填充靠近尾部的区域

内容的提问来源于stack exchange，提问作者HatCreater1