关于裁料算法的优化

简化的问题：  
  1、已知多种预定尺寸的材料（比如长度分别为1米、2米、5米等的木料），每种材料的单位价格不同（通常小尺寸的材料单价比较高）  
  2、已知某个或者多个订单中的材料需求（比如需要0.3米的材料m根，0.5米的材料n根等等）  
  如何求得最佳的裁料结果？该结果通常是成本最低的结果。  
   
  如果采用遍历法，那程序写法不难，但是当订单中需求数量非常大的时候，效率就很成问题了。不知各位有没有什么好的办法。谢谢！ 问题点数：300、回复次数：29Top

1 楼Riemann（）回复于 2003-01-06 13:16:15 得分 40

这是一个整数规划的问题，常用的方法有割平面法，分枝定界法等，具体细节你可以找本运筹方面的书看看。Top

2 楼KingSunSha（弱水三千）回复于 2003-01-06 19:57:12 得分 0

谢谢楼上，能不能具体一点？Top

3 楼KingSunSha（弱水三千）回复于 2003-01-07 18:32:58 得分 0

算法版好像没什么人，转到这里会不会热闹一点？  
   
  这个问题在实际中有很大的实用价值，比如服装套裁问题的解决、集装箱装箱的优化等等。诚心请教，欢迎大家讨论。Top

4 楼TheAres（班门斧）回复于 2003-01-07 19:17:28 得分 40

这不就是贪婪算法吗?    
  这个就是,有一个伪代码.  
  http://202.113.96.10/ini/arithetics/No11.htm  
   
  不过,这个比较一般的还少复杂那么一点点.就是木头头可以不要.  
  比如,一米的木头,分成3个0.3米的,剩下0.1是不是可以不要了?(某些情况下这样真可能节省成本)  
  要不要考虑锯一段木头所用的费用?(比如人力,工具消耗).  
   
  需要代码吗?我的计算机上只有C#编译器.Top

5 楼chenbinghui（阿炳）回复于 2003-01-07 19:34:55 得分 30

好象要找到一个通用的方法还是比较难，对单个问题可能简单一点，  
  象一维的情况还好说，如果是2d,3d那就比较麻烦，  
  贪婪算法不是很好，  
  模拟退火算法还要更好一点  
   
  http://www.ciom.ac.cn/xxzx/Publication/gxjmgc/1999/9904/990403.htmTop

6 楼GiantHard（展翅）回复于 2003-01-07 21:01:40 得分 20

书　名：   数据结构、算法与应用C++语言描述    
  作     者：   （美）Sartaj   Sahni    
  出版社：   机械工业出版社  
  很好的类似问题参考书  
  Top

7 楼KingSunSha（弱水三千）回复于 2003-01-07 21:04:31 得分 0

谢谢各位，我不需要具体的代码，只要有算法或者伪代码就行。  
   
  我看看你们给的文章先。Top

8 楼KingSunSha（弱水三千）回复于 2003-01-07 21:12:23 得分 0

请问楼上有电子书下载吗？Top

9 楼TheAres（班门斧）回复于 2003-01-07 21:25:08 得分 0

[灌水]To   KingSunSha(弱水三千):  
  问你个问题吧,   贵公子叫孙昂还是另有含义?   现在在哪?是瑞典吗?  
   
  没有看到上面哪本的电子本.Top

10 楼saucer（思归）回复于 2003-01-07 23:38:09 得分 40

sound   like   you   are   looking   for   a   backpack   algorithm,   search   on   google.com:  
  http://www.google.com/search?hl=en&lr=&ie=UTF-8&oe=UTF-8&q=backpack+algorithm&btnG=Google+Search  
   
  A   Fast   and   Efficient   Solution   to   the   Backpack   Problem  
  http://www.edm2.com/0601/backpack.htmlTop

11 楼KingSunSha（弱水三千）回复于 2003-01-08 03:24:04 得分 0

to   TheAres(班门斧)：  
  犬子名孙昂，一者因慕陈子昂高才，二者纪念我与太太的母校。现蜗居瑞典，日日寒风酷雪，然妻儿在侧，虽寒冷而犹感温馨。  
   
  蒙saucer(思归,   MS   .NET   MVP)兄眷顾，荣宠无比。  
  Top

12 楼KingSunSha（弱水三千）回复于 2003-01-08 18:54:36 得分 0

正在学习和尝试中，欢迎大家继续讨论。Top

13 楼yarshray（saga jion(心飘情落)）回复于 2003-01-08 20:22:24 得分 40

http://soft.km169.net/soft/html/1606.htm  
   
  这个希望对你有些帮助  
   
  里面的算法很全面.有破解文件.Top

14 楼houjianxun（三千溺水)(独取一瓢清泉）回复于 2003-01-08 20:43:01 得分 10

关注Top

15 楼yarshray（saga jion(心飘情落)）回复于 2003-01-08 20:50:43 得分 0

下料算法,也许这篇文章有点用  
   
  如下;  
   
  http://chenxs.cn.gs/paper2.doc  
   
  我觉得大家应该把自己的观点阐述出来这样回对问题  
   
  的实质有帮助.希望大家来讨论.(我本人对算法不厉害,所以更多的是  
   
  来学习的,希望得到各位的提协)Top

16 楼yarshray（saga jion(心飘情落)）回复于 2003-01-08 21:35:14 得分 0

思归的思路是对的,  
   
  这确实应该象背包问题靠拢  
   
  应该按这个出发点来思考.Top

17 楼KingSunSha（弱水三千）回复于 2003-01-08 23:12:24 得分 0

下面是我的一些思路：  
  已知条件：  
  1、n种材料，长度（或者容量）分别为m_len(i)，成本为cost(i)，1<=i<=n  
  2、x个订单，每个订单需要的长度为o_len(i)，1<=i<=x，其中max(o_len)<max(m_len)  
  要求结果：  
  1、每种材料所需的数量m_qty(i)，1<=i<=n。并使sum(m_qty(i)*cost(i))趋近最低  
  2、基于以上方案对订单的分组，使得以上方案是可行的  
   
  解题思路：  
  1、根据每个订单的长度，可以获得所有订单长度的总和m_ttl_len=sum(o_len)。  
   
  2、现在问题变成了类似于背包问题，但不是简单的(1/0)背包问题，而是较为复杂的(y/0)背包问题。因为在我的实际问题中，n不是很大，所以即使采用穷举法，性能也不是很大的问题（当然我相信看了新的提示，应该有更优化的算法）。假定现在得到了一个结果集：  
  方案     材料1数量       材料2数量   ...   材料n数量       总成本  
  1                         a1                     b1   ...                 c1         cost1  
  2                         a2                     b2   ...                 c2         cost2  
  3                         a3                     b3   ...                 c3         cost3  
  ...  
   
  3、根据上面获得的结果集，从最小成本方案开始验证该方案是可行的（即至少有一种方法来对订单进行分组），对此采用回溯算法中类似的解决方案（谢谢TheAres(班门斧)给出的文章）进行判断。如果方案被证实是可行的，那就采用该方案，否则继续判断下一个方案。。。  
   
  还没来得及具体写代码测试，有任何结果我会和大家共享。Top

18 楼qqchen79（知秋一叶）回复于 2003-01-09 01:37:51 得分 30

Backpack   is   a   classic   NP   problem,   which   means   the   complexity   of   finding   the   best   solution   is   at   least   O(N*N).   When   N   gets   bigger,   theoretically   there   is   no   way   to   solve   the   problem   within   an   accepable   time.   Not   mention   that   here   we   want   to   extend   the   problem   into   3   dimensions   (It's   still   NP,   though).  
   
  On   the   other   hand,   there   are   always   many   heuristic   algorithms   which   may   give   some   acceptable   results   (may   or   may   not   be   the   best)   in   a   reasonable   time.Top

19 楼qqchen79（知秋一叶）回复于 2003-01-09 01:47:52 得分 0

一般对于这样的NP问题，解决的思路是：  
  1)   采用启发性的算法（背包问题的解法通常已经包含了启发性）。  
  2）限定算法执行时间，仍然采用穷举，返回给定时间内找到的最好结果。Top

20 楼qiujoe（迷糊）回复于 2003-01-09 11:12:11 得分 20

我觉得TheAres(班门斧)   提出要不要考虑锯木头的费用是一个实际的问题，如果不考虑就一直用单价低的材料好了：-)  
  我想应在材料数量不同时采用不同的算法  
  1。当单价低的材料很多时，优先使用单价的材料  
  2。当所有材料尺寸与材料需求的尺寸相差不大时采用尺寸匹配算法  
  (基于一个假设，5米的材料锯成一米以后和预定尺寸1米的材料差不多，我想也应该差不多，否则肯定有一种材料会很少用：-)  
   
  学习Top

21 楼benbencatrabbit（笨笨猫）回复于 2003-01-12 18:37:46 得分 5

upTop

22 楼colin666（边缘）回复于 2003-01-13 11:54:45 得分 5

upTop

23 楼jordano7832（康师傅）回复于 2003-01-13 17:52:43 得分 5

这么多星星啊！学习！Top

24 楼chenbinghui（阿炳）回复于 2003-01-13 21:39:07 得分 5

最近稍微看了一下遗传算法(ga)，觉得还是模拟退火法解决上面的问题比较好一点，Top

25 楼HellMaster（李晋）回复于 2003-01-13 22:27:17 得分 5

upTop

26 楼imports（小鸡快跑!Q_Q）回复于 2003-01-13 22:39:51 得分 5

又上了一堂《数据结构》的课！  
   
  Top

27 楼KingSunSha（弱水三千）回复于 2003-01-14 03:00:21 得分 0

不好意思，最近几天很忙，没有空研究这个问题，等稍空下来再深入。谢谢大家的热心讨论！Top

28 楼Riemann（）回复于 2003-01-15 11:11:09 得分 0

原来这贴跑到这儿来了，还得我好找，偶一般知在算法版闲逛。  
  to   KingSunSha(弱水三千)：  
        你的思路是正确的，不过用回溯的方法求解却不是一种好办法。正如偶在前面所说的，我觉得用分枝定界法可以大大提高求解的效率。分枝定界法可以参考：     http://202.113.96.10/ini/arithetics/No55.htm  
   
   
  Top

29 楼link800（寸白虫）回复于 2003-01-15 14:02:00 得分 0

运筹学,我学过,学的自以为还不错.  
  运筹学,真的挺有用Top

相关问题

• 算法
• 代码
• google
• 材料
• backpack
• 法
• 木头
• 比如
• 问题
• 成本

• 帖主：KingSunSha
• Riemann
• TheAres
• chenbinghui
• GiantHard
• saucer
• yarshray
• houjianxun
• qqchen79
• qiujoe
• benbencatrabbit
• colin666
• jordano7832
• chenbinghui
• HellMaster
• imports

• CSDN .NET频道
• .NET类图书
• C#类图书
• .NET类源码下载