ボックスのスタック - 動的プログラミング

Question

私は現在、いくつかの動的プログラミングを練習中です。私はBox of Stackを見つけました。
ボックスは、のように表される：

struct Box{ 
    double h; 
    double w; 
    double d; 
}; 

問題は、スタック内の各ボックスは、その上よりも（幅および深さの両方において）、大きい箱の最高スタックを作成しています。この場合、ボックスは回転できないとします。

私はボックスをstd::vector<Box>に保存しています。私は最初に幅と深さで安定した並べ替えをしています。そのため、ボックスを選択するたびに、次に収まるボックスを前方に検索する必要があります。

これは私の質問です - 最適ですか？
私はボックスを選ぶたびに、次のボックスを選択するために線形時間（O（n））を検索する必要があると思います。
時間の複雑さが改善される可能性のあるボックスを保存する方法はありますか？

他の最適化ももちろん歓迎します。

---

私の完全なコード：

//Get index of next box that fits or -1 if none 
int getP(std::vector<Box>& boxes, int n){ 
    double n_w = boxes[n].w; 
    double n_d = boxes[n].d; 
    for (int i=n-1; i >= 0; i--){ 
     if (n_w > boxes[i].w && n_d > boxes[i].d) 
      return i; 
    } 
    return -1; 
} 

//Get highest possible stack. 
double stackOfBoxes(std::vector<Box>& boxes, int n, Box* bottom){ 
    if (n == -1) 
     return 0; 
    if (bottom == NULL || (bottom->d > boxes[n].d && bottom->w > boxes[n].w)) 
     return max(stackOfBoxes(boxes, n-1, bottom),stackOfBoxes(boxes, getP(boxes,n), &boxes[n])+boxes[n].h); 
    else 
     return stackOfBoxes(boxes, n-1, bottom); 
} 


int main(){ 
    std::vector<Box> boxes = { {3,1,1},{5,2,2},{10,7,7} }; 
    std::stable_sort(boxes.begin(), boxes.end(), sortByW); 
    std::stable_sort(boxes.begin(), boxes.end(), sortByD); 

    cout << stackOfBoxes(boxes, 2, NULL) << endl; 
} 

Answer 1

そして、ここでは私の質問ですが - この最適ですか？

間違っています。

0.5の3番目のボックスの奥行きを除いて、同じ入力でコードを試しました。

Here is the result。それは他の箱が第3のものの上に合うことができないので答えが10であるべき15を与える。

Answer 2

サブ問題の最適解を現在の（n番目の）ボックスを含むように拡張できると仮定しているため、コードは実際には正しくありません。

例：{2, 50, 1}, {1, 1, 2}, {1, 3, 3}

（上記の例では、2種類によって変更されていません）あなたのアルゴリズムのgetP(boxes, 3)は2番目のボックス、{1, 1, 2}は、最終{1, 3, 3}ボックスを先行することができる最新のボックスであることを、正しく、決定します、サブプロキシstackOfBoxes(boxes, 1)の解決方法を尋ねることにより、呼び出しコードは、ボックスがリストの2番目のボックスの前（つまり、最初のボックスまたは2番目のボックス）の前に来ると仮定して、最終的に{1, 3, 3}ボックスしかし、それは真実ではありません。 stackOfBoxes(boxes, 1)は最終的に正しく2を返します。これは最初のボックスでのみ達成できますが、外側のstackOfBoxes(boxes, 2)呼び出しは、50> 3という事実にもかかわらず、最後の{1, 3, 3}ボックスを追加することができると考えています。

stackOfBoxes(boxes, n)の返り値がを意味することを非常に明確にするのに役立ちます。ここでコードをどのように記述したかは、「< = n」のボックスのみを使用するボックスの有効なスタック（サブシーケンス）によって達成できる最大の高さを意味する必要があります。この問題の定式化は、残念ながら最適な部分構造を導くものではない。（ただし、行う他の製剤が存在する。）

（バグの私の以前の説明でバグを見つけるためのNelxiostのおかげで！）