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

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)時間內工作。