java - 嵌套框算法 - 基于嵌套娃娃但根本不同？

Question

我试图解决与 SPOJ 嵌套玩偶问题相关的问题，其中使用具有二维底部的盒子而不是在单个比例参数上不同的玩偶。我有一个算法，但我对问题背后的实际理论以及是否存在更好的方法感到非常困惑。谁能帮助我更好地理解问题并找到更好的算法？

作为复习，嵌套娃娃问题如下:

给定 N 个不同大小的 Matryoshka 玩偶，找到将这些玩偶最佳嵌套后剩余的最小嵌套玩偶数量。对于每个嵌套玩偶，如果最外面的玩偶大小为 S，则它要么不包含任何玩偶，要么包含一个大小严格小于 S 的嵌套玩偶。

我不知道这个问题的全部细节，但通过阅读它，我相信嵌套玩偶问题可以通过增加大小对玩偶进行排序并从大小序列中重复提取最长递增子序列 (LIS) 来解决，通过选择使用最大玩偶的子序列来打破平局。嵌套娃娃的数量将是提取的子序列的数量。我认为这种贪心算法之所以有效，是因为:

a) 减少其中一个子序列的长度会引入新的玩偶，这些玩偶不能减少在未来步骤中发现的嵌套玩偶的数量(“越少越好”)

b) 替换子序列中的一个玩偶必然会将剩余玩偶集合中的一个较小的玩偶替换为一个较大的玩偶，这不能减少在未来步骤中找到的嵌套玩偶的数量(“越小越好”)

这意味着可以使用良好的 LIS 算法在 O(N log N) 中解决该问题。

但是盒子问题是不同的:给定 N 个具有不同底部尺寸的开放盒子，找到将盒子最佳地相互嵌套后剩余的最少数量的盒子堆叠。对于每个盒子堆，如果最外面的盒子有尺寸 WxH 那么它要么不包含盒子，要么包含一个盒子堆，其宽度和高度都严格小于分别比 W 和 H。

这意味着盒子没有总顺序 - 如果盒子 A 不适合盒子 B，这并不意味着盒子 B 的尺寸与 A 相同，或者它可以放入盒子 A，这与 Matryoshka 娃娃不同。

我不知道我是否正确，但我认为不再可以通过重复提取 LIS(或者更确切地说，最长的盒子序列)来找到最佳解决方案，主要是因为没有断绝关系的好方法。如果我们在 1x17 盒子和 5x4 盒子之间进行比较，那么面积较大的盒子最终可能对 future 的步骤更有用。尝试所有绑定(bind)的 LIS 听起来像是指数运行时间。我是对的，还是真的有一种贪婪的方式来做到这一点？

我只找到了一篇关于此的帖子 ( Stacking boxes into fewest number of stacks efficiently? )，它建议使用图论方法来解决问题。我对图论的经验很少，所以我不知道这种方法是如何工作的。我基本上盲目地接受了他们的话来制作一个二分图的盒子，断言盒子堆叠的数量=(盒子的数量 - 最大匹配的大小)。然后我在没有完全理解它实际上是如何解决问题的情况下，基于伪代码在 Java 中实现了 Fork Fulkerson 算法。我已尽力用我的思维过程对代码进行注释，但令我恼火的是这种方法与 Nested Dolls 解决方案有何不同，而且当我被要求在 1 小时内完成此操作时需要 150 多行代码。真的没有更简单的方法来解决这个问题吗？

代码:

import java.util.*;

public class NestedBoxes {
    private static final int SOURCE_INDEX = -1;
    private static final int SINK_INDEX = -2;

    private NestedBoxes() {
        // Unused
    }

    public static void main(String args[] ) throws Exception {
        // Get box dimensions from user input
        Scanner sc = new Scanner(System.in);
        int numBoxes = sc.nextInt();
        List<Rectangle> boxes = new ArrayList<>();
        for (int i = 0; i < numBoxes; i++) {
            Rectangle box = new Rectangle(sc.nextInt(), sc.nextInt());
            boxes.add(box);
        }

        // Sort boxes by bottom area as a useful heuristic
        Collections.sort(boxes, (b1, b2) -> Integer.compare(b1.width * b1.height, b2.width * b2.height));

        // Make a bipartite graph based on which boxes fit into each other, and
        //  add a source linking to all boxes and a sink linked by all boxes.
        // Forward edges go from the left (lower index) nodes to the right (higher index) nodes.
        // Each forward edge has a corresponding backward edge in the bipartite section.
        // Only one of the two edges are active at any point in time.
        Map<Integer, Map<Integer, BooleanVal>> graphEdges = new HashMap<>();
        Map<Integer, BooleanVal> sourceMap = new HashMap<>();
        graphEdges.put(SOURCE_INDEX, sourceMap);
        graphEdges.put(SINK_INDEX, new HashMap<>()); // Empty adjacency list for the sink
        for (int i = 0; i < numBoxes; i++) {
            // TreeMaps make the later DFS step prefer reaching the sink over other nodes, and prefer
            //  putting boxes into the smallest fitting box first, speeding up the search a bit since
            //  log(N) is not that bad compared to a large constant factor.
            graphEdges.put(i, new TreeMap<>());
            // Each node representing a box is duplicated in a bipartite graph, where node[i]
            //  matches with node[numBoxes + i] and represent the same box
            graphEdges.put(numBoxes + i, new TreeMap<>());
        }
        for (int i = 0; i < boxes.size(); i++) {
            // Boolean pointers are used so that backward edges ("flow") and
            //  forward edges ("capacity") are updated in tandem, maintaining that
            //  only one is active at any time.
            sourceMap.put(i, new BooleanPtr(true)); // Source -> Node
            graphEdges.get(numBoxes + i).put(SINK_INDEX, new BooleanPtr(true)); // Node -> Sink
            for (int j = i + 1; j < boxes.size(); j++) {
                if (fitsIn(boxes.get(i), boxes.get(j))) {
                    BooleanVal opening = new BooleanPtr(true);
                    graphEdges.get(i).put(numBoxes + j, opening); // Small box -> Big box
                    graphEdges.get(numBoxes + j).put(i, new Negation(opening)); // Small box <- Big box
                }
            }
        }
        Deque<Integer> path; // Paths are represented as stacks where the top is the first node in the path
        Set<Integer> visited = new HashSet<>(); // Giving the GC a break
        // Each DFS pass takes out the capacity of one edge from the source
        //  and adds a single edge to the bipartite matching generated.
        // The algorithm automatically backtracks if a suboptimal maximal matching is found because
        //  the path would take away edges and add new ones in if necessary.
        // This happens when the path zigzags using N backward edges and (N + 1) forward edges -
        //  removing a backward edge corresponds to removing a connection from the matching, and using extra
        //  forward edges will add new connections to the matching.
        // So if no more DFS passes are possible, then no amount of readjustment will increase the size
        //  of the matching, so the number of passes equals the size of the maximum matching of the bipartite graph.
        int numPasses = 0;
        while ((path = depthFirstSearch(graphEdges, SOURCE_INDEX, SINK_INDEX, visited)) != null) {
            visited.clear();
            Integer current = SOURCE_INDEX;
            path.pop();
            for (Integer node : path) {
                // Take out the edges visited.
                //  Taking away any backward edges automatically adds back the corresponding forward edge,
                //  and similarly removing a forward edge adds back the backward edge.
                graphEdges.get(current).get(node).setBoolValue(false);
                current = node;
            }
            numPasses++;
        }

        // Print out the stacks made from the boxes. Here, deleted forward edges / available backward edges
        //  represent opportunities to nest boxes that have actually been used in the solution.
        System.out.println("Box stacks:");
        visited.clear();
        for (int i = 0; i < numBoxes; i++) {
            Integer current = i;
            if (visited.contains(current)) {
                continue;
            }
            visited.add(current);
            boolean halt = false;
            while (!halt) {
                halt = true;
                System.out.print(boxes.get(current));
                for (Map.Entry<Integer, BooleanVal> entry : graphEdges.get(current).entrySet()) {
                    int neighbor = entry.getKey() - numBoxes;
                    if (!visited.contains(neighbor) && !entry.getValue().getBoolValue()) {
                        System.out.print("->");
                        visited.add(neighbor);
                        current = neighbor;
                        halt = false;
                        break;
                    }
                }
            }
            System.out.println();
        }
        System.out.println();

        // Let a box-stack be a set of any positive number boxes nested into one another, including 1.
        // Beginning with each box-stack being a single box, we can nest them to reduce the box-stack count.
        // Each DFS pass, or edge in the maximal matching, represents a single nesting opportunity that has
        //  been used. Each used opportunity removes one from the number of box-stacks. so the total number
        //  of box-stacks will be the number of boxes minus the number of passes.
        System.out.println("Number of box-stacks: " + (numBoxes - numPasses));
    }

    private static Deque<Integer> depthFirstSearch(Map<Integer, Map<Integer, BooleanVal>> graphEdges,
                                           int source, int sink, Set<Integer> visited) {
        if (source == sink) {
            // Base case where the path visits only one node
            Deque<Integer> result = new ArrayDeque<>();
            result.push(sink);
            return result;
        }

        // Get all the neighbors of the source node
        Map<Integer, BooleanVal> neighbors = graphEdges.get(source);
        for (Map.Entry<Integer, BooleanVal> entry : neighbors.entrySet()) {
            Integer neighbor = entry.getKey();
            if (!visited.contains(neighbor) && entry.getValue().getBoolValue()) {
                // The neighbor hasn't been visited before, and the edge is active so the
                //  DFS attempts to include this edge into the path.
                visited.add(neighbor);
                // Trying to find a path from the neighbor to the sink
                Deque<Integer> path = depthFirstSearch(graphEdges, neighbor, sink, visited);
                if (path != null) {
                    // Adds the source onto the path found
                    path.push(source);
                    return path;
                } else {
                    // Pretend we never visited the neighbor and move on
                    visited.remove(neighbor);
                }
            }
        }
        // No paths were found
        return null;
    }

    // Interface for a mutable boolean value
    private interface BooleanVal {
        boolean getBoolValue();
        void setBoolValue(boolean val);
    }

    // A boolean pointer
    private static class BooleanPtr implements BooleanVal {
        private boolean value;

        public BooleanPtr(boolean value) {
            this.value = value;
        }

        @Override
        public boolean getBoolValue() {
            return value;
        }

        @Override
        public void setBoolValue(boolean value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "" + value;
        }
    }

    // The negation of a boolean value
    private static class Negation implements BooleanVal {
        private BooleanVal ptr;

        public Negation(BooleanVal ptr) {
            this.ptr = ptr;
        }

        @Override
        public boolean getBoolValue() {
            return !ptr.getBoolValue();
        }

        @Override
        public void setBoolValue(boolean val) {
            ptr.setBoolValue(!val);
        }

        @Override
        public String toString() {
            return "" + getBoolValue();
        }
    }

    // Method to find if a rectangle strictly fits inside another
    private static boolean fitsIn(Rectangle rec1, Rectangle rec2) {
        return rec1.height < rec2.height && rec1.width < rec2.width;
    }

    // A helper class representing a rectangle, or the bottom of a box
    private static class Rectangle {
        public int width, height;

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

        @Override
        public String toString() {
            return String.format("(%d, %d)", width, height);
        }
    }
}

Answer 1

是的，有一个更简单(也更有效)的解决方案。

让我们按宽度对框进行排序(如果两个框的宽度相同，则按高度的相反顺序排序)。很明显，我们只能将一个盒子嵌套到它后面的盒子中。因此，我们想把它分成多个递增的子序列(现在只考虑高度)。有一个定理说，一个序列可以拆分成的递增子序列的最小个数等于最长非递增子序列(即非严格递减子序列)的长度。

总结起来，解决方案是这样的:

1. 按宽度对框进行排序。如果宽度相同，则按高度倒序比较。

2. 丢掉宽度，只计算最长的非递增高度子序列的长度(按照我们排序后得到的顺序)。这是问题的答案。就是这样。

很明显，如果实现得当，该解决方案可以在 O(N log N) 时间内运行。