如何正確高效地執行大小項目網格排序？

Question

所以我有一個2D網格是這樣的...

// Y: Size 13 For Each Column 
// X: Size 9 For Each Row 
vector<vector<int>> grid; 

它與空項目初始化成13的高度，寬度9格。

想象一下我們下面填入下列項目的電網......

1. 3寬度5在X = 0身高項目，Y = 0。
2. 2寬度5高度項目在X = 3，Y = 0。
3. 2寬度5 X = 5時的高度項，Y = 0。
4. 2寬度5高度項在X = 7，Y = 0。
5. 2寬度5 X = 0處的高度項，Y = 5。
6. 2寬度5高度項目在X = 2，Y = 5。
7. 2寬度5 X = 4時的高度項，Y = 5。
8. 3寬度5高度項目，X = 6，Y = 5。

現在想象一下，我們需要一種功能，將重新組織庫存到最好的，最節省空間，佈局。這正是我需要的。雖然我不能確定如何做到這一點...

目前我瓶坯使用下面的函數和函數調用排序...

bool SortBySize(const InventoryItem &lhs, const InventoryItem &rhs) 
{ 
    Item itemL = GetItemByName(lhs.item); 
    Item itemR = GetItemByName(rhs.item); 

    return itemL.cells() > itemR.cells(); 
} 
// In Main()... 
sort(m_items_list.begin(), m_items_list.end(), SortBySize); 

然而，這安排導致一些項目不能被移動/排序，因爲重新排序後沒有足夠的空間容納該項目。在這種特定情況下，2個3x5項目首先被存儲，然後所有2x5項目都會跟着它們。但是，網格將不適合新的排序順序的2x5項目之一，這會導致一些意外的行爲...

Answer 1

您可以將此視爲垃圾箱裝箱問題。這個問題是NP-complete，因此沒有已知的有效方法來找到解決方案。解決這個問題的一種方法是從左上角最大的一塊開始（0,0）。然後剩下的兩件做同樣的事情。 Code inComplete中有這個過程的不錯的example。它處理包裝CSS精靈，但應該很容易在C++中對此解決方案進行修改。