盒子堆疊算法

Question

我有一個盒子堆疊算法疑問，在這裏建議： http://people.csail.mit.edu/bdean/6.046/dp/

算法做一些錯誤的假設： 在視頻方面，它說，我們「中的順序箱排序降低基地面積......等「。 我們這樣做是因爲只有當放置在上方的盒子的寬度和深度分別小於下盒子的寬度和深度時，盒子才能放在另一盒子的頂端。 ，但是如果框B_1的底部區域大於框B_2，那並不意味着它的寬度和深度也大於框B_2的寬度和深度。例如，具有1x8基部尺寸的盒子具有比具有2x3尺寸的盒子更大的底部區域，但仍然：1 < 2（和1 < 3），因此我們不能將盒子B_2堆疊到B_1上。 我在這裏錯過了什麼？

Answer 1

這是一個必要條件與充分條件的問題。確實，您可能會遇到無法將B_2堆疊在B_1上的情況，但在這種情況下，B_1也無法堆疊在B_2上，因此在按順序切換它們時沒有任何價值。也就是說，如果B_a比B_b具有更大的基數，我們知道B_a不能堆積在B_b上（因爲它至少有一個維度違反約束條件）。

換句話說：在最佳的盒子堆棧中，所有盒子都是按照減少的基地面積排序的。因此，如果所有盒子的列表都是按減少的基礎面積排序的，那麼最佳堆棧就是所有盒子列表的子序列 - 當然，這個序列只包含前面的k個盒子。這意味着，根據動態規劃的要求，當檢查方框k時，方框k可以依賴的最優籌碼已經在前一輪中生成。

Answer 2

這是如何呈現，但整個問題是找到一個序列，您可以應用LIS（最少增加的子序列）是令人困惑的。