切割股algo - c＃實現

Question

我正在尋找一個c＃解決方案或算法爲Cutting Stock Problem。我的要求是如下：

1. 我將得到的片材說1000 * 1000（W * H）
2. 我需要將其切成3片的150 * 200，300 * 250，275 * 300
3. 我需要找到最佳的解決方案，以最大限度地減少這些線的數量，即浪費應該是最小的，數量應該是最大的！

任何指向任何c＃文件的指針或鏈接都會非常有幫助。

P.S：我已經找過關於這個問題的先前的問題，我還沒有找到任何C＃代碼或任何算法步驟將其轉換爲C＃代碼。

Answer 1

切割庫存問題是已知的NP難題。在合理的時間內無法達到有保證的最佳解決方案。

作爲您給出狀態的鏈接，如果您不必擔心整數解決方案（第一類矩形的1.2部分），則可以應用Gilmore和Gomory方法。

否則，你可以考慮在互聯網上提供許多啓發式。以下是二維裝箱算法的鏈接： How is 2D bin packing achieved programmatically?

注意：切割庫存問題和裝箱問題之間存在細微但重要的區別。你將不得不相應地調整算法。