將1維長度嵌套到預定庫存長度的有效算法是什麼？1維嵌套算法
例如，如果需要在以下的數量和長度的鋼條，
- 5×2米
- 5×3米
- 5×4米
和這些可以從10米酒吧切割。 如何計算切割10米鋼筋的模式，以便使用最小數量的鋼筋？
另外，如何將多個股票長度合併到算法中？
我已經有一段時間來處理這個問題，所以我要寫下我是如何解決它的。我希望這會對某人有用。我不確定是否可以像這樣回答我自己的問題。如果更合適，主持人可以將其更改爲答案。
首先感謝所有回答的人。這使我指出了適當的算法; the cutting stock problem。
此帖子內容同樣有用; "Calculating a cutting list with the least amount of off cut waste"。
好的，在解決方案。
我將在我的解決方案中使用以下術語;
- 庫存：材料的長度將被切成小塊
- 剪切：材料的長度已經從庫存切斷。可能會從同一塊原料中進行多次切割。
- 廢料：所有切割完成後留在一塊原料中的材料長度。
有解決問題的三個主要階段，
- 找出所有可能的切割組合
- 確定可以從每一塊的股票
- 採取組合可切割的最佳搭配組合。
步驟1
隨氮素切口，有2^N-1獨特的剪裁組合。這些組合可以表示爲二元真值表。
其中A，B，C是唯一切割;
A B C | Combination
-------------------
0 0 0 | None
0 0 1 | C
0 1 0 | B
0 1 1 | BC
1 0 0 | A
1 0 1 | AC
1 1 0 | AB
1 1 1 | ABC
帶有一些按位運算符的for循環可用於快速創建每個剪切組合的分組。
這可以得到相當耗費時間在我的情況有相同剪輯的多個實例N.
的較大值。這產生了重複的組合。
A B B | Combination
-------------------
0 0 0 | None
0 0 1 | B
0 1 0 | B (same as previous)
0 1 1 | BB
1 0 0 | A
1 0 1 | AB
1 1 0 | AB (same as previous)
1 1 1 | ABB
我能夠利用這種冗餘來減少計算組合的時間。我將重複剪輯分組在一起，並計算出該組的獨特組合。然後，我將這個組合列表附加到第二組中的每個獨特組合，以創建一個新組。
例如，切割AABBC的過程如下。
A A | Combination
-------------------
0 1 | A
1 1 | AA
調用此基團X
追加X到B的獨特實例，
B B X | Combination
-------------------
0 0 1 | A
| AA
0 1 0 | B
0 1 1 | BA
| BAA
1 1 0 | BB
1 1 1 | BBA
| BBAA
呼叫該組Y.
追加ÿ至C的獨特實例，
C Y | Combination
-----------------
0 1 | A
| AA
| B
| BA
| BAA
| BB
| BBA
| BBAA
1 0 | C
1 1 | CA
| CAA
| CB
| CBA
| CBAA
| CBB
| CBBA
| CBBAA
這個例子le產生17個獨特組合而不是31（2^5-1）。節省近一半。
一旦所有的組合都被識別出來，現在是時候檢查它是如何適應股票的。
步驟2
該步驟的目的是在步驟1到的可用庫存尺寸識別的切割組合進行映射。
這是一個相對簡單的過程。 對於每個切口組合，
calculate the sum of all cut lengths.
for each item of stock,
if the sum of cuts is less than stock length,
store stock, cut combination and waste in a data structure.
Add this structure to a list of some sort.
這將導致有效的切割嵌套組合的列表。 由於這可以根據切割長度和庫存長度來計算，因此不必嚴格儲存廢物。但是，在步驟3中
步驟3
在此步驟中，我們將鑑定產生最少的浪費切口的組合所需的處理存儲浪費減少。這是基於步驟2中生成的有效巢的列表。
在理想的世界中，我們將計算所有可能性並選擇最佳的一個。對於任何不平凡的裁剪組合，都需要永久計算。我們只需要滿足一個非最優解決方案。 有完成這項任務的各種算法。
我選擇了一種方法，尋找一個浪費最少的巢。它會重複這一點，直到所有削減已經計入。
開始與三個列表
- cutList：所有必需的削減（包括重複）的列表。
- nestList：步驟2中生成的嵌套列表。這是從最低廢物到最高廢物排序。
- finalList：最初爲空，這將存儲將輸出給用戶的剪切組合列表。
方法
pick nest from nestList with the least waste
if EVERY cut in the nest is contained in cutList
remove cuts from cutList
copy this nest into the finalList
if some cuts in nest not in cutList
remove this nest from nestList
repeat until cutlist is empty
用這種方法，我設法得到大約2-4％的總浪費一些典型的測試數據。希望我會在某個時候重新討論這個問題，並且着手實施Delayed column generation算法。這應該會有更好的結果。
我希望這可以幫助其他人解決這個問題。
大衛
這看起來像一個作業問題非常多... – 2008-10-06 13:48:59
也許它不是作業 - 這非常像一個實際的工業問題，我寫了一個程序回到1990年左右 – DarenW 2008-10-06 14:50:12
我使用了不同的算法。結果可以在http://wood-cut.rhcloud.com上看到。它沒有給出最佳解決方案，因爲它需要枚舉方法，但提供了可接受的解決方案。我看到一些軟件以超過50美元的價格提供這些軟件，並使用遺傳算法，並且不保證最佳解決方案，有時甚至比http://wood-cut.rhcloud.com的結果更差。我正在努力優化我的網站，並在我獲得時間時編寫該算法。 – 2013-05-24 06:15:25