計算窗口套管的高效使用（裝飾）

Question

我正在研究一個應用程序，該應用程序將爲我的業務估算建築材料。我現在正在處理的部分專門處理繞過窗口的修剪。

解釋這一點，最好的辦法是舉一個例子：

窗裝飾購買在14英尺（168英寸）的長度。假設我有5個不同尺寸的長方形窗戶，每個長方形窗戶均由4件裝飾物組成（頂部和底部，以及左右）。我正試圖建立一種算法來確定以最少的浪費來切割這些碎片的最佳方法。

我已經研究過使用排列來計算每個可能的結果並跟蹤浪費，但排列的數量超過萬億一旦我通過5個窗口（20個不同的修剪）。

有沒有人對我如何做到這一點有所瞭解。

謝謝。

Answer 1

您正在查看cutting stock problem的典型案例。

我覺得this lecture from the University of North Carolina (pdf)比較清楚。更多的以實現爲導向，以一個例子貫穿始終，而且要求很少 - 可能只是查找幾個縮略詞。但也有2 hours of video lectures from the university of Madras的話題，如果你想了解更多的細節和相當緩慢的步伐。

它依靠求解the knapsack problem幾次，如果你不想經歷第二個線性優化問題，你可以抓住directly from Rosetta Code。

總之，你想選擇一些方法（每個長度有多少塊）來削減庫存（在你的情況下，窗口修剪），以及每種方式使用多少次。

你從一個微不足道的組合開始：對於你需要的每一個長度，制定一個只有這個尺寸的切割方法。然後你重複：揹包問題給你從當前配置中減少庫存的最不利的方法，然後單純形法從你的減少庫存的方式中「移除」這個組合。

Answer 2

爲了優化在Windows和雙摺門的窗扉，爲公司我工作了，我用這個簡單的矩陣 - 我只是採取了最常見的開口，並決定什麼是最合理，最優化的切割長度。

例如，通過使用一個8'切口和一個12'切口，可以利用廢物修剪3050窗口。