您的位置：程序门 -> vb -> 基础类

高分求教算法：一维下料问题（星星们快来，请过路高手留下脚步，分留着也没用，权当散分)

[收藏此页] [打印本页]选择字色：背景色：字体：[大][中][小]

高分求教算法：一维下料问题（星星们快来，请过路高手留下脚步，分留着也没用，权当散分)

发表于：2007-05-24 17:22:16 楼主

最近公司有一个关于自动配料方面的软件，由小弟接手，关于算法部分苦思不得其解，望各位大哥大姐赐教。具体如下：
假设：
库存中有4m*3、6.5m*5、7m*5、8m*10、10m*8（4m*3表示4米的材料有3根)，
现在用户需要3m*3、3.5m*1、4m*4、5m*3。

问用户该怎么取材，才能使浪费余料最少？

可以认为库存里最长的材料肯定比用户需要的最长的材料长。

浪费余料：就是在本次切割过程中，切割下来的，但没有用在本次用户要求上的材料都算浪费余料

可参见：http://community.csdn.net/expert/topic/5525/5525732.xml?temp=.0393793
和
http://community.csdn.net/expert/topic/5516/5516559.xml?temp=.9682733
和
http://community.csdn.net/expert/topic/5516/5516559.xml?temp=.7672846

发表于：2007-05-24 20:14:531楼得分:0

1.先找最匹配的,不用切隔的.比如4m*4 可以从4m*3中分配3,余1待分配
2.找两个相加可以匹配的.比如5m*3+3m*3可以从8m*10中分配得到
3.找最接近的,或者两个相加最接近的.比如3.5m*1+4m*1最接近8m*1.
这样余料只有0.5m*1

发表于：2007-05-25 02:30:352楼得分:0

分别使用“最佳匹配”“最差匹配”计算结果。然后比较浪费量。
最佳－每个的余量最小开始
最差－每个的余量最大开始

这个算法和会议持续时间类似。

发表于：2007-05-25 07:51:073楼得分:0

估计这个计算比较复杂,

定义一个余料的变量

从用户需求中,取出奇数的材料,如313,都减1,去查找材料库

用去6.5*1,10*1（余5*1+10*7+4*3+6.5*4+7*5+8*10)
还需用料3*2,4*4,5*2

取奇数材料35（5m,3m)
用去5*1,8*1,还差一个3m*1+4*4

余料得10*7+4*3+6.5*4+7*5+8*9

取奇数1和 1
用去7*1+4*3,余料10*7+6.5*4+7*4+8*9

不浪费

发表于：2007-05-25 07:51:464楼得分:0

具体的用料算法可以自己算

发表于：2007-05-25 07:52:135楼得分:0

最少余料也自己统计,应该是最少的了

发表于：2007-05-25 08:11:576楼得分:0

chuting（学习的动力) （ ) 信誉：101 blog 加为好友

看不懂你的意思，但有那么容易分解吗？

发表于：2007-05-25 08:13:127楼得分:0

to:cathysun118（斯年)
请参见提到的其他贴子。

发表于：2007-05-25 08:38:448楼得分:0

记的是典型的数学问题。

发表于：2007-05-25 08:51:529楼得分:0

这个问题好久前就提出来了,还没有得到解决?
看来是有些难度

发表于：2007-05-25 08:54:0910楼得分:0

这是世界8大数学难题之一，复杂的算法往往很浪费时间，应该在优化率和效率上找个平衡点。

发表于：2007-05-25 09:00:3811楼得分:0

//这是世界8大数学难题之一

有那么夸张吗？

我也知道可能以目前已有的算法来说解不出最优解（除非材料很少的情况下用穷举)。

但是希望可以找到优化率高些的解

发表于：2007-05-25 11:00:2312楼得分:0

发表于：2007-05-25 11:51:2113楼得分:0

我对你这个题有点郁闷：
如果用户需要6m*1，
你库存有10m，7m，4m，假如拿出一根10m切割，剩下4m不是可以并入库存吗，这个也算浪费吗？？但是按照你的要求，只能从7m切割，那样就浪费1m………
这个题求算法，难就难在，根本没有界定性，或者说，你的界定本身就存在不合理的地方，很难求最优解。

发表于：2007-05-25 12:11:4814楼得分:0

这个界定就是：
浪费余料：就是在本次切割过程中，切割下来的，但没有用在本次用户要求上的材料都算浪费余料

发表于：2007-05-25 12:12:3515楼得分:0

//所以你库存有10m，7m，4m，假如拿出一根10m切割，剩下4m不是可以并入库存吗，这个也算浪费吗？？

剩下4m就算浪费。即切割后的不会并入库存

发表于：2007-05-25 12:20:1316楼得分:0

但是你这样设计是明显的不合理嘛。。。

发表于：2007-05-25 14:34:1617楼得分:0

并非不合理。而是实际中就是这样。。。

发表于：2007-05-25 14:46:5318楼得分:0

有趣 mark

发表于：2007-05-25 15:01:0819楼得分:0

我看要列出几种方案

a,余料最少

b,切割最少

c,焊接最少

d,还没想到.....

列出后再看看应该在什么情况下选用某一组.....如果有规律,才可以用程序完成....

发表于：2007-05-25 15:07:4620楼得分:0

看在200分的分上帮楼主一把。按照楼主所想，可以这样做：
1、首先根据用户需要材料的总长度得到需要从仓库中最多拿出多少根材料才能满足用户的总长度。比如（3*3+3.5*1+4*4+5*3)/4=10.875,然后用进一法得到11根。
2、把仓库中所有的材料（即每一根）作为全组合里总数，用步骤1得到的数作为每一组的数字个数。比如总数为3＋5＋5＋10＋8=31，那么就要计算c31 11，得到每一种组合。
3、得到每一种组合后对每一种组合进行计算，如果能够满足用户的要求，则把此种组合分割的方法保存下来，如果此组浪费的材料比先前的组浪费的材料多，就可以排除。
4、对于每一组的计算，则采用排列的方法，首先计算出用户所需材料的总数3+1+4+3=11。然后对这11根材料进行全排列得到p11，计算出每一组排列。
5、在得出用户材料的全排列后，用步骤3得到的某一组（cn）去计算是否能满足要求，满足要求后剩余多少，这个就是简单的用某一组依次减去用户排列的每一个元素，如果cn的某个元素不够长了，用cn此元素的下一个元素去减。每减去一个用户排列的元素，这个元素就排除在外。
6、经过步骤5，满足条件的就可以列出来了，估计最后会有n组数据，但是可以根据要求再增加条件，这个楼主仔细考虑一下就好了。
7、以上的算法是枚举法复杂度过高，但一般都是这么做的。如果想提高速度，可以将全组合分成几个部分，每部分由一台计算机计算，最后将结果汇总。
8、关于如何动态的得到cn m的计算方法，这个在csdn上是有的，楼主可以搜索以前的帖子，具体是在算法那个类。

发表于：2007-05-25 17:46:2321楼得分:0

本次提问的要求是仅考虑：怎样才能使浪费余料最少

发表于：2007-05-25 17:51:2522楼得分:0

to yunyu97（)
看到第一步就有问题了：
1、首先根据用户需要材料的总长度得到需要从仓库中最多拿出多少根材料才能满足用户的总长度。比如（3*3+3.5*1+4*4+5*3)/4=10.875,然后用进一法得到11根。
库存里有：6m*2,现需要4*2、3*1

按你的第一步：4*2+3，则是11m。那我给你6m*2> 11，你看能不能切割出来。

发表于：2007-05-25 17:54:4023楼得分:0

而且你算法的时间复杂度是不可以想像的。。。也许要n个月或者n年才能解出来。

发表于：2007-05-25 17:56:0624楼得分:0

//以上的算法是枚举法复杂度过高，但一般都是这么做的。如果想提高速度，可以将全组合分成几个部分，每部分由一台计算机计算，最后将结果汇总。

这个也太夸张了。网格计算？

发表于：2007-05-26 10:03:1925楼得分:0

呵呵.....算法不简单....

帮顶一下.....

发表于：2007-05-27 13:52:5026楼得分:0

to lgyan（紫衣随想)
我给你的算法是有条件的，是在仓库中的材料一定可以不用焊接的情况下给出的算法，如果需要焊接，你可以在我的算法的基础上改进的。
另外我想告诉你一点，算法的复杂度的可行性不是说凭想象的，而是要你自己去试验的，只有试过才知道是否可行，我可以确切的告诉你，我给你的算法还是可以再进一步优化的。我做过彩票软件，彩票软件就是这样一组一组进行筛选的，1000多万组也就几十秒，何况你这个每一组使用的计算方法都是很简单的。而且你的需求还不一定需要把所有的方法都试出来，只要能够满足要求就可以了，难道不是么？
不是什么问题都有快捷的方法的，只要能够满足需求即可。我们能够做的就是在已有的基础上不断的进行优化。
关于网络计算的问题，如果你这个系统有n台计算机联网，每台计算机的计算量就是1/n，这一点都不困难，只要在计算前分配好数据给每台计算机，然后通知下面开始计算，再要做的就是等待每台计算机把结果返回过来。那些号称512位加密的东东不就是这样被几万台计算机破解的么，更何况你这么点数据。

发表于：2007-05-27 15:09:0227楼得分:0

晕，1000多万组的数据要用几十秒，够慢的了。。。
扫描比较120m的数据也就大概花2秒左右的时间。

发表于：2007-05-27 15:14:5728楼得分:0

http://www.vbgood.com/viewthread.php?tid=50194&extra=page%3d1
我写的大概60行左右的代码，测试kpm扫描的，1秒可以扫描比较40-60m的数据。

发表于：2007-05-27 15:23:4529楼得分:0

我测试了一下，1000万组双色球数据大概在55.6m。
我觉得，如果用yunyu97的方法生成组合，然后筛选，应该是可行的，关键是自己要确立好筛选的条件。。

发表于：2007-05-28 08:24:4530楼得分:0

to:
2、把仓库中所有的材料（即每一根）作为全组合里总数，用步骤1得到的数作为每一组的数字个数。比如总数为3＋5＋5＋10＋8=31，那么就要计算c31 11，得到每一种组合。

c31是库存材料的总长度，但实际上库存材料都是上万米的。c10000 11计算时间会是多少？？考虑过没。

即使时间可允许，那么你如何去判断一种组合可不可以分解成所需要的长度？？你的4、5两步我看不懂

发表于：2007-05-28 09:14:5631楼得分:0

你要仔细看清楚我的算法，c31不是材料的总长度，而是总数目，与长度无关。如果仓库的材料数目，即每一种类型的材料数大于步骤1所计算出来的数，那么仓库的材料总数可以看作以步骤1的11为基数×材料的类型数目。
另：如果你不能理解我的算法，我可以给你讲解，但如果你不相信我的算法，那我就没有说的必要了。我还是那句话，没有试过就不能证明。

发表于：2007-05-28 10:52:0132楼得分:0

实在不理解你的算法，总数目，与长度无关？
你可以举个简单的例子来描述你算法的思想吗？
或者加qq:79938938

发表于：2007-05-28 10:52:1933楼得分:0

谢谢你的参与

发表于：2007-05-28 12:53:0334楼得分:0

发表于：2007-05-28 14:09:5835楼得分:0

这个好象是数学里最优化算法,我不会~~
学习下

发表于：2007-05-28 19:33:0436楼得分:0

难度大

发表于：2007-05-29 09:18:2637楼得分:0

发表于：2007-05-29 17:39:1238楼得分:0

星星在哪里？

发表于：2007-05-29 17:50:3139楼得分:0

能力有限从前回答过

发表于：2007-05-30 11:25:2040楼得分:0

从前回答过？是什么意思？从前解决过？

发表于：2007-05-31 09:22:5941楼得分:0

其他资讯