動態編程：盒子堆疊變化

Question

我們有n個盒子，其尺寸是x，y，z（寬度，高度，深度）。 我們想插入最大數量的盒子。
如果內框（i）的尺寸嚴格小於外框（j）的尺寸，則可以將框放在另一框內：x [i] < x [j]，y [i] < y [j]，z [i] < z [j]。
箱子不能旋轉，可以按任何順序考慮。

我怎樣才能實現與動態規劃的目標是什麼？
該問題類似於時間最長的子序列問題？
按升序/降序排列盒子是否合理？

Answer 1

這裏是C++一個簡單的自上而下的方法：

#include <iostream> 
#include <vector> 
#include <algorithm> 
#include <climits> 

using std::cin; 
using std::cout; 
using std::vector; 
using std::ostream; 

// G[i][j]==true if box i will fit inside box j. 
// L[i] is the number of boxes that will fit inside box i, or -1 if 
//  this value has not been determined. 

// Calculate how many boxes will fit inside box j. 
static int count(const vector<vector<bool>> &G,vector<int> &L,int j) 
{ 
    int n = L.size(); 
    int max_x = 0; 

    for (int i=0; i!=n; ++i) { 
     if (G[i][j]) { 
      if (L[i]==-1) { 
       L[i] = count(G,L,i); 
      } 
      int x = L[i]+1; 
      if (x>max_x) { 
       max_x = x; 
      } 
     } 
    } 

    return max_x; 
} 


int main() 
{ 
    int n; cin >> n; 
    vector<int> x(n+1), y(n+1), z(n+1); 

    for (int i=0; i!=n; ++i) { 
     cin >> x[i] >> y[i] >> z[i]; 
    } 

    // Add a huge box that contains any box 
    x[n] = INT_MAX; 
    y[n] = INT_MAX; 
    z[n] = INT_MAX; 

    vector<vector<bool> > G(n+1,vector<bool>(n+1,false)); 

    for (int i=0; i!=n+1; ++i) { 
     for (int j=0; j!=n+1; ++j) { 
      G[i][j] = x[i]<x[j] && y[i]<y[j] && z[i]<z[j]; 
     } 
    } 

    vector<int> L(n,-1); 

    // Print the number of boxes that will fit in the huge box. 
    cout << count(G,L,n) << "\n"; 
} 

有多種方法，使這個速度更快，但是這顯示了遞歸形式允許使用動態規劃。

Answer 2

上的框執行拓撲排序，將它們安排成一個曲線圖，如下所示：每個盒子處於圖中的節點，從節點A到節點B中的每個定向弧指示對應的盒A持有盒B.擴大此結構中有一個無限大小的盒子和一個零大小的盒子。

作爲拓撲排序，該曲線圖將是一個有向非循環圖。因此，找到最長的路徑是而不是 NP-hard，而是可以在O（V + E）中解決。您的兩個擴充框之間最長的路徑包含問題的答案。

設置排序爲O（V^2），從排序圖中查找解爲O（V + E），在這種情況下爲O（V^2），這是您的總體解決時間。