問題描述如下：
1）n段長度不一的管子；
2）m段長度不一的需求，從1）中截取；
3）2）中的所有需求，不允許有介面；
4）完成需求后，1）中的管子剩余長度小于200的即為浪費；
5）如1）中存在長度比例懸殊的管子（長/短>=10），短的剩余在100以內的情況，優于長的無浪費的情況。
如上，如何找到最優解：浪費總長度最小，且短的優先使用。
簡化一下，假如我已計算出所有能完成需求的方案，那么如何從這些方案中找到最優。
方法原型如下，planList是所有能完成需求的方案，從planList中找到最優解：
Plan func(list<int> n, list<int> m,list<Plan> planList);
class Plan{
list<PlanStep> steps;
}
class PlanStep{
int mIndex;//需求下標
int nIndex;//原材料下標
int length;//截取長度
}
uj5u.com熱心網友回復：
一般意義上的最優解是沒有辦法得到的，因為該問題cutting stock problem（優化下料問題）是NP-hard。NP-hard簡單的說，就是沒有多項式的解法。或許你應該追求‘可滿意’的解法，或可接受的解法，而不是最優解。
如果你有學術上的興趣，可以自行搜索“優化下料問題”，也可以先閱讀如下文章，先了解問題深淺：
【一維優化下料問題】，張春玲，崔耀東
http://manu28.magtech.com.cn/Jweb_gllg/CN/article/downloadArticleFile.do?attachType=PDF&id=1744
【型材下料問題演算法研究】，劉潤濤，陳媛婧
http://cea.ceaj.org/CN/article/downloadArticleFile.do?attachType=PDF&id=25348
uj5u.com熱心網友回復：
的確，“最優解”存在主觀意識。
“可滿意”表述更正確。
uj5u.com熱心網友回復：
學習一下框架 Microsoft.SolverFoundationuj5u.com熱心網友回復：
排料演算法是NP Hard的，（在資料規模比較大的情況下）只能求近似最優https://download.csdn.net/download/wh2623/9863860
uj5u.com熱心網友回復：
看來此問題，接觸過的人不多，雖然只有幾個回帖，但是得到了很多有用資訊，比如“一維下料”、“cutting stock problem”、“NP-hard”等。從這些資訊了解到問題的研究方向。于是各種看碩士論文，這些論文中提到了很多“高大上”的演算法用來解決該問題，而且論文中的試驗結果也非常漂亮。于是我用論文中的演算法做了如下嘗試：1、窮舉法：此演算法最常規，但是復雜度大，而且隨著原料數量的增加，時間復雜度成指數級增長，根本無法用于生產；
2、遺傳演算法：完全跟著論文做，跑出來的結果跟論文中的結果相差甚遠，無法再生產中使用。這些東西也就是用來畢業的。
3、蟻群演算法：不敢再跟著論文做了，未做深入研究，不過我估計，也是用來糊弄老師的
4、線性規劃：可能會有效果，未做研究。
最后，本人研究出一套自創演算法，簡單有效，用戶用了都說好。這里不方便說了，涉及到一些商業上的東西。有感興趣的可以私信聯系。
忠告：不要盲目相信一些論文，時間搭進去，結果卻出不來。
uj5u.com熱心網友回復：
今天優化了演算法，整體思想簡單來說就是模擬人工下料的程序。學術論文研究了那么多年寫了那么多論文，基本是瞎搞不切合實際而且我十分懷疑資料造假。
uj5u.com熱心網友回復：
遺傳、蟻群這些演算法本質也就是窮舉，只是有方向的窮舉，效果應該不會太差，引數可能沒配置好。實際工程上可能材料切割長度沒有那么多變化，最優解憑經驗早就試出來了，演算法上省下來的那一點點浪費不值得
uj5u.com熱心網友回復：
你的這類問題太簡單了，其實不值得撰寫程式。真正的問題有時候有200個變數，100多個約束條件，用 Excel 或者 Microsoft.SolverFoundation 求解，幾秒鐘完成。uj5u.com熱心網友回復：
如果問題大一點兒，例如 n >=200，而 m>=100，并且還有 m*k 個其它需求約束條件，你還能用經驗法去湊出來答案嗎？uj5u.com熱心網友回復：
以前解決的方法，其實未去考慮什么大神的演算法，只是按實際生產中作業中可操作的方法來的先切最長的，剩下的端頭，從余下的需求中去查是否還有可用，如果沒有，是否滿足廢料要求，是否有保留長度大于多少可保留以后用的要求
這樣就可以了
uj5u.com熱心網友回復：
引數調了又調，還是挑不出來。生產中問題很復雜，原料規格不一，需求規格不一，一個好的切割方案和一個一般的切割方案，廢料差積累下來還是很可觀。并且憑經驗算出的方案大概率是一個一般甚至比一般更差的方案，并且很燒腦、耗時耗工。
uj5u.com熱心網友回復：
大神，我很想知道怎么用excel或Microsoft.SolverFoundation完成這個事兒。確實原料規格最大也就200了，零件規格最多也就100左右。
uj5u.com熱心網友回復：
貼一組資料：
方案1：
余 1，排樣規則：3514=3513
余 4，排樣規則：4549=4545
余 10，排樣規則：4688=4678
余 0，排樣規則：3490=3490
余 1，排樣規則：10962=2448+3959+4554
余 1，排樣規則：9013=2270+1609+5133
余 1，排樣規則：7917=4568+3348
余 4，排樣規則：12186=4002+2467+5713
余 9，排樣規則：10403=3627+2447+4320
余 1，排樣規則：9056=2280+3690+3085
余 0，排樣規則：14219=5392+4900+3927
余 0，排樣規則：14704=3933+2221+4524+4026
余 2，排樣規則：9044=1894+4336+2812
余 1，排樣規則：14673=4550+4844+5278
余 1，排樣規則：7614=3740+3873
余 1，排樣規則：11532=3812+1670+3577+2472
余 1，排樣規則：10784=4031+3320+3432
余 2，排樣規則：8871=3950+4919
余 0，排樣規則：12701=5336+2981+4384
余 0，排樣規則：10267=4054+3760+2453
余 0，排樣規則：8538=1668+4403+2467
余 2，排樣規則：6024=3348+2674
余 1，排樣規則：13225=2864+2946+4327+3087
余 5，排樣規則：12734=4635+3828+1988+2278
余 0，排樣規則：27656=2701+5619+1775+4535+4161+3138+5727
余 2，排樣規則：23865=2355+5548+5422+4339+2997+3202
余 3，排樣規則：18251=4812+3298+5386+4752
余 1，排樣規則：17717=3222+3020+4010+4156+3308
余 0，排樣規則：21608=5156+4898+3988+2968+1986+2612
余 1，排樣規則：18706=2779+5709+4040+2149+4028
余 1，排樣規則：28280=5576+2921+5594+4320+4137+5731
余 0，排樣規則：19110=3101+3677+2809+1784+4130+3609
余 3，排樣規則：19147=3860+2582+1600+1725+5122+4255
余 4，排樣規則：21970=5536+2411+3489+4018+3816+2696
余 0，排樣規則：17030=5593+1997+5151+4289
余 2，排樣規則：16586=5549+2282+3642+5111
余 2，排樣規則：26366=2985+4600+4265+1845+4996+3395+1768+2510
余 4，排樣規則：25215=4641+5370+5722+5438+4040
余 3623，排樣規則：23952=3241+1656+3568+2398+5621+3845
余 8592，排樣規則：18678=5512+4574
方案2：
余 14，排樣規則：3973=3959
余 1，排樣規則：3514=3513
余 4，排樣規則：4549=4545
余 10，排樣規則：4688=4678
余 12，排樣規則：3113=3101
余 18，排樣規則：4659=4641
余 0，排樣規則：3490=3490
余 15，排樣規則：4884=1784+3085
余 5，排樣規則：10962=2453+3020+3202+2282
余 0，排樣規則：9013=3950+1668+3395
余 0，排樣規則：7917=2270+2946+2701
余 0，排樣規則：12186=4156+3627+4403
余 0，排樣規則：10403=2221+2812+5370
余 6，排樣規則：9056=4996+4054
余 4，排樣規則：14219=2968+5621+2278+3348
余 0，排樣規則：14704=2997+5713+2696+3298
余 0，排樣規則：9044=5111+3933
余 0，排樣規則：14673=3690+5727+2447+2809
余 1，排樣規則：7614=3740+3873
余 2，排樣規則：11532=4010+5122+2398
余 0，排樣規則：10784=4600+3320+2864
余 0，排樣規則：8871=4752+1609+2510
余 1，排樣規則：12701=5536+4026+3138
余 4，排樣規則：10267=4574+3222+2467
余 0，排樣規則：8538=4289+1894+2355
余 2，排樣規則：6024=3348+2674
余 0，排樣規則：13225=3489+4320+1600+3816
余 2，排樣規則：12734=3568+5133+4031
余 1，排樣規則：27656=4002+4524+1775+3927+4844+3432+5151
余 5，排樣規則：23865=4535+3642+3677+2612+3845+5549
余 3，排樣規則：18251=5594+5512+4161+2981
余 0，排樣規則：17717=2149+5576+5438+4554
余 6，排樣規則：21608=3241+4339+5392+2921+5709
余 0，排樣規則：18706=4336+3828+5156+5386
余 2，排樣規則：28280=4635+4040+5422+4130+5731+4320
余 2，排樣規則：19110=1656+2411+3988+4040+4028+2985
余 0，排樣規則：19147=2472+4255+4265+4137+4018
余 8，排樣規則：21970=5548+5278+1725+4327+1997+3087
余 5，排樣規則：17030=5722+1988+4568+2280+2467
余 1，排樣規則：16586=4550+5593+2582+3860
余 1，排樣規則：26366=1768+5619+2779+4898+4384+3308+3609
余 1，排樣規則：25215=3577+1670+4919+4812+5336+4900
余10101，排樣規則：23952=2448+3812+1986+3760+1845
方案3：
余 14，排樣規則：3973=3959
余 1，排樣規則：3514=3513
余 27，排樣規則：4627=4600
余 4，排樣規則：4549=4545
余 10，排樣規則：4688=4678
余 12，排樣規則：3113=3101
余 18，排樣規則：4659=4641
余 0，排樣規則：3490=3490
余 6，排樣規則：4884=1656+3222
余 4，排樣規則：10962=2472+3642+4844
余 0，排樣規則：9013=1894+2221+4898
余 3，排樣規則：7917=4054+3860
余 6，排樣規則：12186=3489+4535+4156
余 2，排樣規則：10403=2448+3927+4026
余 6，排樣規則：9056=2280+1670+1668+3432
余 0，排樣規則：14219=4265+4568+5386
余 2，排樣規則：14704=3577+4040+3395+3690
余 0，排樣規則：9044=2612+2864+3568
余 2，排樣規則：14673=3085+2510+5336+3740
余 3，排樣規則：7614=2674+2355+2582
余 0，排樣規則：11532=1725+3627+4031+2149
余 7，排樣規則：10784=4028+3828+2921
余 0，排樣規則：8871=3760+5111
余 0，排樣規則：12701=5512+2270+4919
余 1，排樣規則：10267=3308+1988+1768+3202
余 5，排樣規則：8538=4130+4403
余 4，排樣規則：6024=2411+3609
余 1，排樣規則：13225=5549+4327+3348
余 2，排樣規則：12734=2812+4384+5536
余 2，排樣規則：27656=5548+2779+3298+4752+2467+3845+1997+2968
余 1，排樣規則：23865=4812+4018+4161+4574+1775+4524
余 0，排樣規則：18251=4137+3241+5151+5722
余 1，排樣規則：17717=3087+5727+4002+4900
余 0，排樣規則：21608=2981+4554+4040+5713+4320
余 1，排樣規則：18706=2278+5370+5438+5619
余 7，排樣規則：28280=5392+2453+3138+2467+5709+2282+3812+3020
余 0，排樣規則：19110=5422+4255+2696+2398+4339
余 0，排樣規則：19147=5576+2701+1600+3677+5593
余 4，排樣規則：21970=1609+4336+5621+5122+5278
余 6，排樣規則：17030=3988+2985+5731+4320
余 1，排樣規則：16586=4550+2946+3933+5156
余 1，排樣規則：26366=5133+4996+2997+2809+2447+4635+3348
余 4，排樣規則：25215=3816+4289+1784+3873+5594+1845+4010
余14696，排樣規則：23952=3950+3320+1986
方案4：
余 14，排樣規則：3973=3959
余 1，排樣規則：3514=3513
余 27，排樣規則：4627=4600
余 4，排樣規則：4549=4545
余 10，排樣規則：4688=4678
余 12，排樣規則：3113=3101
余 33，排樣規則：3906=3873
余 18，排樣規則：4659=4641
余 0，排樣規則：3490=3490
余 6，排樣規則：4884=1656+3222
余 0，排樣規則：10962=4161+2985+3816
余 6，排樣規則：9013=5709+3298
余 12，排樣規則：7917=2467+5438
余 2，排樣規則：12186=3860+2812+5512
余 7，排樣規則：10403=4130+2946+3320
余 3，排樣規則：9056=2612+2701+3740
余 1，排樣規則：14219=3202+3609+4320+3087
余 0，排樣規則：14704=4919+4026+2674+3085
余 10，排樣規則：9044=5392+3642
余 0，排樣規則：14673=4255+4535+1768+1668+2447
余 0，排樣規則：7614=5336+2278
余 0，排樣規則：11532=4635+1997+4900
余 1，排樣規則：10784=2864+2398+1894+3627
余 1，排樣規則：8871=4550+4320
余 2，排樣規則：12701=5722+4524+2453
余 0，排樣規則：10267=4018+4028+2221
余 2，排樣規則：8538=5727+2809
余 4，排樣規則：6024=2779+3241
余 2，排樣規則：13225=5370+2467+5386
余 0，排樣規則：12734=2282+4031+4010+2411
余 4，排樣規則：27656=5536+5621+4568+5156+1775+4996
余 1，排樣規則：23865=1670+2981+3950+3933+1600+2997+3812+2921
余 2，排樣規則：18251=3927+3690+4752+2448+3432
余 0，排樣規則：17717=2270+4844+1609+1986+4040+2968
余 1，排樣規則：21608=4137+4002+4336+4040+2510+2582
余 0，排樣規則：18706=3308+3828+4403+4812+2355
余 3，排樣規則：28280=3489+2472+5619+1784+2696+3677+4156+4384
余 1，排樣規則：19110=3020+4898+5151+2280+3760
余 0，排樣規則：19147=3138+4554+5593+1988+1725+2149
余 0，排樣規則：21970=5731+5278+4265+3348+3348
余 0，排樣規則：17030=5713+1845+4339+5133
余 1，排樣規則：16586=3395+4574+4327+4289
余 9，排樣規則：26366=3988+3568+5576+5594+4054+3577
余 40，排樣規則：25215=5111+5122+3845+5548+5549
余18530，排樣規則：23952=5422
方案5：
余 14，排樣規則：3973=3959
余 1，排樣規則：3514=3513
余 27，排樣規則：4627=4600
余 4，排樣規則：4549=4545
余 10，排樣規則：4688=4678
余 12，排樣規則：3113=3101
余 33，排樣規則：3906=3873
余 18，排樣規則：4659=4641
余 41，排樣規則：4095=4054
余 0，排樣規則：3490=3490
余 12，排樣規則：4884=1670+3202
余 43，排樣規則：3130=3087
余 0，排樣規則：10962=2779+3609+4574
余 2，排樣規則：9013=5713+3298
余 5，排樣規則：7917=1775+2510+3627
余 2，排樣規則：12186=2612+5727+3845
余 2，排樣規則：10403=2582+2270+5549
余 0，排樣規則：9056=3348+2467+3241
余 3，排樣規則：14219=2280+5278+2968+3690
余 3，排樣規則：14704=5512+4554+4635
余 0，排樣規則：9044=2282+3085+3677
余 0，排樣規則：14673=3020+4320+4524+2809
余 1，排樣規則：7614=2467+2472+2674
余 4，排樣規則：11532=4339+1768+1609+3812
余 0，排樣規則：10784=3927+3860+2997
余 2，排樣規則：8871=3138+5731
余 1，排樣規則：12701=4844+4040+3816
余 2，排樣規則：10267=5576+2411+2278
余 0，排樣規則：8538=1656+2864+4018
余 0，排樣規則：6024=1894+4130
余 1，排樣規則：13225=2221+3308+1986+5709
余 6，排樣規則：12734=5621+4752+2355
余 0，排樣規則：27656=4040+5111+4137+2701+5438+1845+4384
余 4，排樣規則：23865=1668+4031+4002+3348+1784+5386+3642
余 0，排樣規則：18251=4320+4336+1600+5548+2447
余 1，排樣規則：17717=3320+5156+1725+3489+4026
余 1，排樣規則：21608=5722+5619+3828+1997+1988+2453
余 1，排樣規則：18706=2985+3395+4535+4568+3222
余 0，排樣規則：28280=3568+2696+5370+2981+5151+5593+2921
余 3，排樣規則：19110=3577+2398+5422+4898+2812
余 0，排樣規則：19147=3740+3950+3760+3432+4265
余 0，排樣規則：21970=4156+2448+4900+4289+4028+2149
余 2，排樣規則：17030=4161+5594+2946+4327
余 3509，排樣規則：16586=4812+4010+4255
余 50，排樣規則：26366=4919+5392+5536+5133+5336
余 22，排樣規則：18678=3988+5122+4996+4550
余10847，排樣規則：19183=4403+3933
方案6：
余 14，排樣規則：3973=3959
余 1，排樣規則：3514=3513
余 27，排樣規則：4627=4600
余 4，排樣規則：4549=4545
余 10，排樣規則：4688=4678
余 12，排樣規則：3113=3101
余 33，排樣規則：3906=3873
余 18，排樣規則：4659=4641
余 41，排樣規則：4095=4054
余 0，排樣規則：3490=3490
余 12，排樣規則：4884=1670+3202
余 43，排樣規則：3130=3087
余 4，排樣規則：10962=3677+3348+3933
余 1，排樣規則：9013=5370+3642
余 1，排樣規則：7917=3577+4339
余 4，排樣規則：12186=3568+4040+4574
余 8，排樣規則：10403=5438+1609+3348
余 0，排樣規則：9056=1845+3816+3395
余 0，排樣規則：14219=1656+2921+3320+2582+3740
余 9，排樣規則：14704=2946+5392+2355+4002
余 3，排樣規則：9044=4752+4289
余 2，排樣規則：14673=3085+4137+4996+2453
余 0，排樣規則：7614=5336+2278
余 6，排樣規則：11532=2398+3828+2280+3020
余 0，排樣規則：10784=2968+4327+3489
余 0，排樣規則：8871=2674+2448+1600+2149
余 18，排樣規則：12701=3609+4524+4550
余 0，排樣規則：10267=3138+2809+4320
余 4，排樣規則：8538=2812+5722
余 1，排樣規則：6024=1768+4255
余 12，排樣規則：13225=2472+5619+5122
余 0，排樣規則：12734=2270+4320+1988+4156
余 2，排樣規則：27656=2467+4554+4336+1775+4812+5549+4161
余 0，排樣規則：23865=4635+3927+4028+5548+5727
余 1，排樣規則：18251=2701+4844+5594+5111
余 1，排樣規則：17717=4898+3812+3298+1668+4040
余 2，排樣規則：21608=4265+3760+4568+3627+5386
余 10，排樣規則：18706=2981+3308+4031+2864+5512
余 10，排樣規則：28280=4919+3432+1784+1986+5536+4900+5713
余 0，排樣規則：19110=2696+3950+2612+1997+3845+4010
余 1，排樣規則：19147=3988+1894+2510+5133+5621
余 0，排樣規則：21970=5151+5422+3222+2411+2779+2985
余 14，排樣規則：17030=5576+5731+5709
余 12，排樣規則：16586=4403+5156+2997+4018
余 3，排樣規則：26366=3860+4384+1725+3241+5278+2282+5593
余 3723，排樣規則：18678=4130+2467+3690+2447+2221
余10622，排樣規則：19183=4535+4026
方案7：
余 14，排樣規則：3973=3959
余 68，排樣規則：4229=4161
余 1，排樣規則：3514=3513
余 27，排樣規則：4627=4600
余 4，排樣規則：4549=4545
余 10，排樣規則：4688=4678
余 12，排樣規則：3113=3101
余 33，排樣規則：3906=3873
余 18，排樣規則：4659=4641
余 41，排樣規則：4095=4054
余 0，排樣規則：3490=3490
余 13，排樣規則：4884=1784+3087
余 45，排樣規則：3130=3085
余 1，排樣規則：10962=3489+3845+3627
余 0，排樣規則：9013=2282+4320+2411
余 1，排樣規則：7917=3348+4568
余 0，排樣規則：12186=3395+3988+2448+2355
余 0，排樣規則：10403=4327+3927+2149
余 0，排樣規則：9056=4919+4137
余 14，排樣規則：14219=4898+5151+4156
余 3，排樣規則：14704=2510+4336+3320+4535
余 6，排樣規則：9044=4635+4403
余 1，排樣規則：14673=4130+3828+2674+4040
余 5，排樣規則：7614=1988+5621
余 3，排樣規則：11532=3677+3298+4554
余 25，排樣規則：10784=2968+3241+4550
余 1，排樣規則：8871=3432+5438
余 1，排
uj5u.com熱心網友回復：
典型的背包問題,樓主可以百度下,有現成演算法uj5u.com熱心網友回復：
問題的核心確實可以對接背包問題。
uj5u.com熱心網友回復：
搭了個demo，有興趣的可以看看：http://106.53.17.139:8088/demo/轉載請註明出處，本文鏈接：https://www.uj5u.com/net/11515.html
標籤：C#
下一篇：獲取支付寶授權用戶資訊