嵌套盒算法 - 基于嵌套玩偶但基本不同？

Question

我试图解决与SPOJ嵌套玩偶问题有关的问题，其中使用的是具有二维底部的框，而不是单个比例参数中不同的玩偶。我有一个算法，但我对这个问题背后的实际理论以及是否存在更好的方法非常混淆。任何人都可以帮助我更好地理解问题，并可能找到更好的算法？

来回顾一下，如下所述嵌套娃娃问题：

鉴于Ñ一个不同大小的俄罗斯套娃，发现保持后最佳地嵌套在彼此内部的玩偶嵌套玩偶的最小数目。对于每个嵌套娃娃，如果最外面的娃娃的尺寸为S那么它不包含娃娃，或者它包含一个尺寸严格小于S的嵌套娃娃。

我不知道这个问题的全部细节，但从阅读的角度来看，我相信嵌套玩偶问题可以通过增加玩偶大小并反复提取最长增加子序列（LIS）来解决。大小的序列，通过选择利用最大娃娃的子序列来打破关系。嵌套玩偶的数量将是提取的子序列的数量。我觉得这个贪心算法的工作，因为：

a）减少这些子序列之一的长度，引入了新的娃娃，可以在不降低未来的步骤（“越少越好”）

二）发现的嵌套娃娃的数量在子序列中替换玩偶必然会用一个更大的玩具娃娃替换剩余玩偶中的较小玩偶，这不会减少在未来步骤中发现的嵌套玩偶的数量（“越小越好”）

这意味着问题可以在O（N log N）中用一个好的LIS算法求解。

但盒子的问题是不同的： 给定N个不同底部尺寸的开放盒子，找到最佳数量的盒子堆叠之后，将盒子相互嵌套。对于每个盒堆叠，如果最外箱具有尺寸W¯¯ X ħ然后它要么不包含盒，或者它包含一个盒堆叠其宽度和高度严格小于W¯¯和ħ分别。

这意味着没有盒子的全部订购 - 如果盒子A不适合盒子B，它并不意味着盒子B的尺寸与A相同，或者它将适合盒子A，这与Matryoshka不同娃娃。

我不知道我是否正确，但我认为通过反复提取LIS（或者说相互配合的盒子的最长序列）可以找到最佳解决方案不再是真的，主要是因为存在没有好办法打破关系。如果我们比较一个1x17盒子和一个5x4盒子，面积较大的盒子仍然可能对未来的步骤更有用。尝试所有绑定的LIS听起来像指数运行时。我是对的，还是真的有一种贪婪的方式来做到这一点？

我只发现了另外一篇文章（Stacking boxes into fewest number of stacks efficiently?），建议使用图论方法来解决这个问题。我对图论的经验很少，所以我不知道这个方法是如何工作的。我基本上盲目地用他们的话来制作盒子的二分图，断言盒子堆栈的数量=（盒子数量 - 最大匹配的大小）。然后我在基于伪代码的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

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

让我们按宽度对它们进行排序（如果两个框的宽度相同，则按其高度相反的顺序）。很明显，我们可以将一个盒子只嵌入一个盒子中。因此，我们想把它分成多个增加的子序列（现在只考虑高度）。有一个定理表明，序列可以分裂成的最小子序列数目等于最长非增长子序列的长度（也就是说，不是严格递减的子序列）。

综上所述，该解决方案是这样的：

1. 排序的箱子它们的宽度。如果宽度相同，则按相反顺序将它们的高度进行比较。

2. 丢掉宽度，只计算最长的非增加高度子序列的长度（按照我们排序后的顺序）。这是问题的答案。而已。

很明显，如果正确实施，此解决方案可以在O(N log N)时间内工作。