問題如下：
條件
1、每根鋼管原材料長6米，原料充足
2、需要成品鋼管長度在0.12米-2米之間不定，需要的根數有2300根，可視為已確定條件
3、切割后可以剩余端頭廢料，剩余端頭廢料越短越好
4、成品鋼管不能拼接
目的
1、利用演算法，將成品鋼管需要的長度分配給6米長的成品鋼管上，使每根6米的鋼管產生的廢料最少。
數學問題描述
從有限個集合內，選出m個元素，使m個元素的和接近6米，選出后的元素從集合中移除，直到集合中沒有元素位置。
是否可以利用組合演算法，然后計算長度是否接近6米。
大神能否給個解決的思路，或者用什么演算法以及組合演算法
uj5u.com熱心網友回復：
沒看懂需求，按照描述都切成1米的就沒有廢料了。是不是你的2300跟長度是已知的啊
uj5u.com熱心網友回復：
大約想了一下，是不是已知有2300根鋼管了，且知道這2300根鋼管分別長多少。uj5u.com熱心網友回復：
若按我理解的2300根鋼管的長度是已知的這個大前提，可以用遺傳演算法計算。將2300根管子編號1-2300，然后采用自然編碼的方式生成基因。按照生成的基因順序取截管子。即幾根管子累加后在加上下一根剛好超過6米時截開(不算下一根管子)，也可以得到廢料長度。評價函式用廢料的總量算。交叉和變異采用傳統方式就可以，這個用遺傳演算法應該很容易實作，效果應該也會很好。uj5u.com熱心網友回復：
可以用貪心演算法，每次都找最接近6米的組合進行剔除。uj5u.com熱心網友回復：
用遺傳演算法做了一下，隨機生成了一組數，利用率能到93%，計算時間大約30秒uj5u.com熱心網友回復：
背包問題，貪心法。uj5u.com熱心網友回復：
典型的背包問題，搜搜吧uj5u.com熱心網友回復：
群主，解決了嗎？uj5u.com熱心網友回復：
一維背包問題，不算難。uj5u.com熱心網友回復：
典型的cutting stock問題，直接建立整數規劃模型求解。大規模情況試試列生成演算法，小規模分支定界法或割平面法都可以。轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/48284.html
標籤：數據結構與算法