Bin包裝算法 - 實際變化

我想解決一個奇怪的箱裝箱問題。一個鏈接，原來的問題是here （抱歉長的問題，感謝您的耐心）Bin包裝算法 - 實際變化

我重新迭代如下問題：我想寫，生成用於條塊面板繪製的應用程序。

我有N個隔間（二維矩形）（N < = 40）。對於每個隔間，都有一個最小高度（minHeight [i]）和最小寬度（minWidth [i]）關聯。面板本身也有一個MAXIMUM_HEIGHT約束。

這些N個櫃子必須一個在另一個的頂部以列方式堆疊，以便每個櫃子滿足上述限制條件。

此外，每列的寬度由該列中每個隔間的最大寬度決定。

此外，每列的高度應該是相同的。這決定了面板的高度

我們可以在任何列中留下的空白處添加備用隔間，或者我們可以將任何隔間的高度/寬度增加到指定的最小值以外。但是我們不能旋轉任何隔間。

OBJECTIVE: TO MINIMIZE TOTAL PANEL WIDTH.

MAXIMUM_HEIGHT面板=2100毫米的，minwidth範圍（350毫米至800mm），範圍了minHeight（225毫米到2100毫米）

按照選擇的答案，我配製整數線性規劃。但是，考慮到問題的組合性質，解決方案似乎在N> 20上「掛起」。

我正在嘗試實施解決方案。

隔間按照minWidths的降序排列。如果minWidths是相等的，那麼它們按照它們的minHeights的降序排序。
然後我使用First Fit decreasing heuristic來解決它。這給了我一個總面板寬度的上限，以及當前列寬度的列表。

現在我試着讓面板寬度變小一點，並嘗試使我的饋線適合那個較小尺寸的面板。（我能夠檢查是否饋線適合在列寬的給定列表以有效的方式）

面板寬度可以做得更小以下列方式：
1.取任何柱，用其替換下一個較低的minWidth進紙器的列。如果該列已經是最小的最小寬度，那麼嘗試刪除它並檢查。
2.取出任何一列，將其替換爲較高的minWidth進紙器的一列，然後移除另一列。
3.任何其他方式，如果有人能指出，我不知道會高興。

我已經正確實施了第一種方法。以下是代碼。但是，我無法正確地將其他代碼放在代碼中。

for (int i = 0; i < columnVector.size(); i++) { 

    QVector<Notepad::MyColumns> newVec(columnVector); 
    if (newVec[i].quantity > 0 
     && (i > 0 || newVec[i].quantity > 1)) { 

     newVec[i].quantity--; 

     if (i < columnVector.size() - 1) 
      newVec[i+1].quantity++; 

     float fitResult = tryToFit(newVec, feederVector); 
     myPanelWidth = fitResult ? fitResult : myPanelWidth;  

     if (fitResult) { // if feeders fit, then start the iteration again. 

      columnVector = newVec; 
      i = -1;  
     }  
    }  
}

任何幫助將不勝感激。

感謝

來源

2013-10-04 Abhishek Bansal