（1）描述：编写程序,从订单中选择一组订单对钢材作切割加工,使钢材得到最佳利用,约定每一次切割会损耗固定长度的钢材（约定该值为2）.已知线型钢材总长度、订单数和各订单需要的钢

Question

（1）描述：编写程序,从订单中选择一组订单对钢材作切割加工,使钢材得到最佳利用,约定每一次切割会损耗固定长度的钢材（约定该值为2）.已知线型钢材总长度、订单数和各订单需要的钢材长度；
（2）输入：钢材总长度s、订单数n、各定单需要的钢材长度；
（3）输出：可以使钢材得到最佳利用的订单号、该订单需要的钢材长度.

Answer 1

对问题进行转化和建模,实际上就是按照最后输出的这组订单序列可以得到钢材最多.于是建模就是这样.假设a1 a2 a3 a4...表示订单需要的钢材长度 其实就是找一个使(a1+a2...+an) 这个多项式值最大的序列,但是又要满足(a1+a2...+an) +(n-1)*2 < L 钢材总长度L
然后就排序枚举就好了. 想优化的话,注意下剪枝就行了.比如要从n=1,开始枚举,每次枚举都先从大往小了枚举,记录每个n值对应的序列和 最大的(a1+a2...+an) 值 若n+1时最大的(a1+a2...+a（n+1）) 比最大的(a1+a2...+an) 小 则停止枚举 (a1+a2...+an) 则为所求