高分求一算法，各位富翁特别是数学高手，帮忙解决.... (200分)

洛

洛吉

Unregistered / Unconfirmed
GUEST, unregistred user!
材料最省的优化算法
条件：
1、有不同长度的标准规格材料
2、需要不同长度的材料
问题：
用这些标准规格的材料截出所有需要的材料，
如何得到最省材料的切割方法？
例如：
有标准规格材料a1=8000,a2=6000,a3=18000,a4=23000,a5=28000,a6=30000,
需要的材料长度有b1=2000,b2=2000,b3=4300,b4=6700。
那么用1条a1切割b4剩余1300
用1条a2切割b3剩余1700
用1条a2切割b2、b3剩余2000
这样切割后多余的材料就是1300+1700+2000 = 5000
如果用1条a3切割b1、b2、b3、b4
这样切割后多余的材料就是18000 - (2000+2000+4300+6700) = 3000
所以第二种方法比第一种更省材料
望富翁们能提供这个算法的流程，当然，有源码更好....
 
有作过一份与这一样的，但代码在家里！
 
我记得在选修课本 数学建模 上看到类似的题目，你找找看
 
ReallyFail,什么时候能发给我吗？
 
代码可能也没办法发9因为公司不也许带这中东西进来，家里头电话又停机了），
不过这不会很难，主要是很烦琐，今晚我在回去看一下，明天在给你讲思路。
不过上面这么多高手，说不定不用到明天就可以解决了。
 
但愿如此，只要富翁们提供算法流程和思路就行了....
 
UP:)
 
我先说个大概：
1。假如待切材料有多种，且材料之间以指定的长度递增并在一定范围的话，
你可以根据结果材料来取得最优的材料。
2。假如无规律的话，你只能将库存中大于结果材料的长度全部读出来，定义一个记录类型
的动态数组。记录类型参考：
tmaterial=record
id:int//数据库中的代号；
length:int//材料长度
count:int//该材料库存量
squander:int浪费长度(也可以用浪费率代替）。
end;
然后对以结果长度对该数组中的材料取摸，算出浪费量（浪费率）
然后找浪费率最小的记录就可以了，如果库存小到要去定货的话那就在去做些修改
基本上能记的得就这写了，不知道在去看代码还要多久才能明白过来[:D][:D]


 
其它富翁都没做过类似的算法吗？
 
打听一下
需要的材料大约有多少,几个,几十个,还是几百个,
精确到数量级就行.
 
需要的材料不固定，标准规格长度的材料也不固定，
相当于是要封装一个对象，给定需要的材料和标准规格长度的材料，
然后找出最佳切割材料的方法.....
 
不用非常精确的话就用贪婪法吧。
 
呵呵，看来我问的不明确.
我知道"需要的材料不固定，标准规格长度的材料也不固定"
我只是问一次运算时,大概有多少个需要的材料,好根据这个数量选择适当的算法.
 
我明白了，你想通过穷举得到一个算法
估计材料需要30、40个吧
标准材料我就不知道了，也许有10多个吧....
希望你能找到一个最优的解决办法，真是谢谢了，
来昆明我请客
 
呵呵，还不至于用穷举。
三四十已经算比较大的了。
标准材料的规模对复杂度的影响很小很小。O(log以2为底的n)
最优的办法可难找了。
去昆明的机会不多。
 
我也是这样想的，同事和我也写了一个算法，
不过我们一致认为应该是一个普遍的问题，
肯定有前辈总结出最好的算法流程，
想问问有没有富翁碰到过这样的算法，
对于是学数学的高人来说可能是一个很简单的算法....
 
我一猜就会在这里看到 LeeChange 老兄
 
两位高人，就帮助研讨解决一下我的问题吧！
 
我可不行，LeeChange很厉害的，向LeeChange学习~~~~~~~~~~~~~
 
您必须登录或注册才可回复。

Similar threads

I
微软面试试题精选
回复
0
查看
605
import
I
I
常用算法（1）贪婪算法
回复
0
查看
617
import
I
I
常用算法（2）分而治之算法
回复
0
查看
668
import
I
I
常用算法（3）动态规划
回复
0
查看
865
import
I
I
常用算法（5）分枝定界
回复
0
查看
583
import
I
顶部