最优地图打印算法

Question

我偶尔会进行长途徒步旅行，经常需要打印 10+ A3 地图。

我正在尝试找到一种算法解决方案来解决打印多条路线地图的手动过程。

手动过程通常不是最佳的，我的意思是页面应该保持在最低限度。例如。添加了额外的页面，就好像我将之前的页面稍微移到了这里和那里，它会在更少的页面中包含该路线。

让事情变得复杂的是，可以在纵向和横向模式下进行打印。

我真的很感谢朝正确方向的推动。有一个简单的解决方案还是需要一些更复杂的思考？

澄清一下：给定一个 2d 点列表，找到它们能容纳的最小盒子数量。盒子可以是 wh（纵向）或 hw（横向）

Answer 1

听起来像是一个完整的搜索问题，你的数组（纸张）大小已经给定，你的路线大小也给定了。你能不能只考虑每一种可能性？ 我认为你的路线只是一个布尔数组，我们只是检查纸张的每一种可能的排列方式，其中没有包含任何内容的部分。我为了好玩编写了一些伪代码，它不是最优化的，但我阻止了它继续下去。您可以在下面参考它。

public mooMap {
    public static void main(String[] args) {
        boolean[][] route = (your map);
        boolean[][] coveredroute = (inverted route array);
        ArrayList<Pair<int>> usedstarts = new ArrayList<>();
        ArrayList<boolean[][]> paper = new ArrayList<>();
        int paperwidth = (your paper's width);
        int paperheight = (your paper's height);
        ArrayList<boolean[][]> mostefficient = new ArrayList<>();
        while(!hasfalse(coveredroute)){
            for (int i = 0; i < route.length; ++i) {
                for (int j = 0; j < route[i].length;++j) {
                    boolean containsroute = false;
                    boolean[][] temp = new boolean[paperwidth][paperheight];
                    for(int k = 0; k < Math.min(route.length-i,paperwidth); ++k) {
                        for(int l = 0; l < Math.min(route[i].length-j,paperheight); ++l) {
                            temp[k][l] = route[i][j];
                            coveredroute[i][j] = coveredroute[i][j] || route[i][j];
                            containsroute = containsroute || temp[k][l];
                        }
                    }
                    if(!containsroute) {
                        continue;
                    }
                    if (usedstarts.contains(new Pair(i,j))) {
                        continue;
                    }
                    paper.add(temp);
                }
            }
        }
        //print out in your preferred format
    }
    static boolean hasfalse(boolean[][] uwu) {
        for (int i = 0; i < uwu.length; ++i) {
            for (int j = 0; j < uwu[i].length; ++j) {
                if(!uwu[i][j]) {
                    return true;
                }
            }
        }
        return false;
    }
    static class Pair<T> {
        public T a;
        public T b;
        public Pair(T a, T b) {
            this.a = a;
            this.b = b;
        }
        public boolean equals(Pair<T> o) {
            return a.equals(o.a) && b.equals(o.b);
        }
    }
}