问题:
厂房里有N根木棍,需要截取出M根型材装入卡车。
木棍的数量任意且可知,长度可能不同且可知,粗细一样且不计。
型材的数量也任意且可知,长度相同且最大化。
只能一根一根的进行一次或几次的截取,不能用几根拼装。
请问:
这个问题是否有解呢?如果有的话,如何计算型材可取的最大长度?计算方法或计算公式是什么呢?有关的图形是怎么样呢?
总体思路:
N根棍子,其长度令为A(1),A(2)...A(N),由小到大排;
要截取出M根;
先任取一个截取长度,比如s
如果 ∑int(A(i)/s)>=M,(其中int为取整数函数),则说明取长度s并没有达到最大化;
则继续取s+1为截取长度,以此类推
最大化的长度S应该满足:∑int(A(i)/S>=M
且 ∑int(A(i)/(S+1))<M
具体解法:
令f(x)=∑int(A(i)/x)-M
取x=1,若f(x)<0,则无解
反之,若f(x)>=0,取x=2,...直到当x=i时,第一次出现f(x)<0,则最优化长度为i-1