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

Question

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

作为补充，嵌套玩偶问题如下：

给定不同大小的N Matryoshka玩偶，找出在将玩偶最佳嵌套后剩余的最小嵌套玩偶数。对于每个嵌套娃娃，如果最外层的娃娃大小为S，则它要么不包含娃娃，要么包含一个大小严格小于S的嵌套娃娃。

我不知道这个问题的全部细节，但通过阅读，我相信嵌套娃娃问题可以通过增加大小来排序娃娃，并从大小序列中反复提取最长增加子序列（LIS）来解决，其中通过选择使用最大娃娃的子序列来断开关系。嵌套玩偶的数量将是提取的子序列的数量。我认为这种贪婪算法有效，因为：

a）减少其中一个子序列的长度会引入新的娃娃，这些娃娃无法减少未来步骤中发现的嵌套娃娃的数量（“越少越好”）

b）替换子序列中的娃娃必然会用较大的娃娃替换剩余娃娃集中较小的娃娃，这不能减少未来步骤中发现的嵌套娃娃的数量（“越小越好”）

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

但是盒子问题是不同的：给定N个底部尺寸不同的打开盒子，找到在最佳嵌套盒子后剩下的最小数量的盒子堆栈。对于每个盒子堆栈，如果最外面的盒子有尺寸WxH，那么它要么不包含盒子，要么包含一个盒子堆栈，其宽度和高度分别严格小于W和H。

这意味着盒子没有总的顺序——如果盒子甲不适合盒子乙，这并不意味着盒子乙和盒子甲的尺寸相同，也不意味着盒子甲适合盒子甲，不像套娃。

我不知道我是否正确，但我认为通过重复提取列表(或者更确切地说，最长的盒子序列)可以找到最优解不再是正确的，主要是因为没有好的方法来打破束缚。如果我们要比较1x17的盒子和5x4的盒子，那么一个面积较大的盒子在以后的步骤中仍然会更有用。尝试所有捆绑的LIS听起来像是指数运行时间。我说的对吗，还是真的有贪心的方法可以做到这一点？

我只找到了另外一篇关于这个的帖子（有效地将盒子堆叠成最少数量的堆叠？），它建议使用图形理论方法来解决这个问题。我对图形理论的经验很少，所以我不知道这种方法是如何工作的。我基本上是盲目地相信他们的话来制作盒子的二分图，断言盒子堆叠的数量=（盒子的数量-最大匹配的大小）。然后，我基于伪代码在Java中实现了Fork Fulkerson算法，但没有完全理解它实际上是如何解决这个问题的。我已经尽了最大努力用我的思维过程来注释代码，但是让我恼火的是，这种方法与嵌套娃娃的解决方案有如此大的不同，当我被要求在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

是的，有一个更简单（和更有效）的解决方案。

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

总而言之，解决方案是这样的:

>

按宽度对框进行排序。如果宽度相同，则按高度的相反顺序进行比较。

抛开宽度，只计算最长的非递增高度子序列的长度（按照我们排序后的顺序）。这就是问题的答案。就这样。

很明显，如果实施得当，此解决方案可以在O（N log N）时间内工作。