最近公司有一个关于自动配料方面的软件，由小弟接手，关于算法部分苦思不得其解，望各位大哥大姐赐教。具体如下：
假设：
库存中有4m*3、6m*5、7m*5、8m*10、10m*8(4m*3表示4米的材料有3根)，
现在用户需要3m*3、4m*4、5m*3、1m*5
问用户该怎么取材，才能使材料的切割次数最少、焊接次数最少？
假设：
库存中有4m*3、6m*5、7m*5、8m*10、10m*8(4m*3表示4米的材料有3根)，
现在用户需要3m*3、4m*4、5m*3、1m*5
问用户该怎么取材，才能使材料的切割次数最少、焊接次数最少？
想了下，大致需要以下步骤
1.先遍历尺码完全匹配的板数，得出不足部分板数
2.切割次数最少优先于焊接次数最少，以不浪费余料为目的，遍历 所需尺码/已有尺码 余数为0的板，找到倍数最接近所需剩余数量的板
3.以上无法匹配的剩余板，则遍历 所需尺码/已有尺码 余数不为0的板，找到最小匹配的板
4.以上无法匹配，则需要焊接，遍历出 只需一次焊接的板，即板A+板B=板c，其次是需要焊接N次的板，直到所有的板达到
4m*1
10m*2=(5m*3+1m*5)
其实不清楚问的是什么.
1、浪费余料最少。
2、切割次数最少。
3、焊接次数最少感谢zlt982001(乐天) 和zzyong00(阿勇)的热情回复
1、zzyong00(阿勇) 所说的问题。
2、假设现需要4m*3，而库存有8m*2和12m*1。此时用算法中的所需尺码/已有尺码，那么8m和12m无疑都是合适的，但实际上应该是12m*1更合适。算法仅考虑了尺码，却没有考虑根数。该算法烦了我几天，没有解决。烦您有空时多考虑考虑。
我QQ：79938938。
至于实现@-@，期待
http://post.baidu.com/f?kz=199426660
//唉。叹息，这种问题回答的这么多竟没有一个说到点子上。楼主给我发信息吧，指点你一下
请联系
我QQ：79938938。
或者[email protected]
所以征解更合适的算法。分不是问题。因为这个算法实在有意思，也应该是实际中经常会用到的。为了我编程的爱好，我一定要找到计算其最优解的最高效的算法望各位兄弟姐妹捧场!
//我去年帮人做过一个,要求基本与你的一模一样,还挣了几百块.可惜代码找不见了.思路是先
//按规格由大到小排序,再由大到小取材,用到了DICTIONARY对象你的算法应该没有考虑到长度组合吧？？
1: 首先去掉库存中相同的。得到一个新的问题。
2: 然后把所有用户需求的长度相加，得到一个自然数A.
3: 从库存中分解自然数A（即把A表示为一些库存中的长度之和），如果可以分解，得到所有分解的组合。不能分解，则求最接近的数据。（具体怎么分解，可以用回朔）。
4：对所有组合，求取焊接次数，求出焊接次数最少的。
5：如果最少焊接次数有相同的，求出切割次数。则切割次数最少的，得到最优解。
其中1，2最简单。3，4，5具体怎么做最好我没想清楚。
大家看看整体思路对不？
你所说的第一步就有问题
假设：用户需要3m*1、4m*1,而库存现有3m*1、7m*1
那么明显是用7m的只需要切割一次，而且切割没有余料产生。
你说的对，如果干脆去掉第一步呢？
第一步反而有问题。没想到...
粗略看一下，
1、算法里没有考虑支数。
可能是我没说明白，这个A =3*3+4*4+5*3+1*5=45..
其实我觉得这样做类似于穷举了..
组合1: 45=10+10+10+10+5=(3+3+3+1)+(4+4+1+1)+(4+4+1+1)+(5+5)+5
这个组合的解决答案为: 余料0 ,切割10,焊接0.
这是一种答案.
所有的组合可以用回朔求出.如果种类和支数不是太多.
这个分解45=10+10+10+10+5可以理解，是拿用户总需求长度不停对库存长度取余整除得来
但10=3+3+3+1
10=4+4+1+1如果得来？
如何可以写成一个算法告诉用户对每种库存长度如何分解？
而且如何计算它的切割次数呢？
刚才看了一下假设：
写了一个分配方案，切割次数为9，余数为0，具体分配如下：
45=10+8+7+7+7+6=(5+5)+(5+1+1+1)+(4+3)+(4+3)+(4+3)+(4+1+1)
现在我想按你的算法，问题可以归纳为对每个长度如何进行分解的问题了？切割次数在分解时就可以计算出来了。
得到了45的一个组合后，以你的结果为例： 10+8+7+7+7+6
１察看是否有相同的，如果有去掉相同的。把需求从大到小排列
２察看是否有２个需求材料的和，如果有，在组合结果和需求中去掉。这里有：
5+5（同时从组合和需求中去掉，切割+1）
5+3,4+3，4+3
3：剩余序列为：7，6剩余需求为4*2+1*4
考虑选择三个 7=4+1+1，6=4+1+1
over
不存在焊接的情况下,可以这么做.
不太清楚步骤1中
//１察看是否有相同的，如果有去掉相同的。
的含义和目的。
隐约感觉还有些情况没有考虑到。
今天先到这，谢谢你了。我现在脑子里象有浆糊，呵。不能继续思考
明天我再想想是否还有其他欠妥的地方
第一步应该去掉了。因为那样会形成一个新的需求。有可能导致求不到最优解。
这个问题有点题意不清楚。我是这样假设的：首先尽量保证没有余料。即从库存中取出来的料都是有用的。（这一步我就不明白，为什么需要这样要求，按说应该有余料放回仓库就是了。应该是尽量避免焊接才是。如果1m是最小单位，不会存在废料呀。）
如果材料数量种类很多。还是用遗传算法好了。组合爆炸起来计算不出来的。
还有：楼主给的例子不具有代表性吧。随便截都没事。反正需要1m的。
本题的假设举的不是很好。当时是随手举的，用来表达问题的意思。没有细想，现在看来，是欠妥了。假设中用户需求1m是不好的。且假设中没有举出小数的例子。实际情况中可能库存会有6.5m等的规格题目要求余料最少优先是因为如下原因：
1、如果是没有这个限制，无法控制短料的产生数量。
2、如果没有这个限制，那么仓库会对长料的需求加大。因为长料好配，也容易切。所以也为了使仓库中各长度的料都能合尽其用。
另外这是个完全NP问题。
你说明了下我有点明白你的意思了：
如果是在实数集上的问题，我也没什么好的想法来求最优。
你可以查找类似的文献，如果材料允许切开了再焊上，确实还能减少余料。
我不知道你说的材料是什么，你说明白了可以查找相关文献。
另外：钢筋有些类似的切割算法，你可以参考下。
我所说的材料就是钢筋。
有类似的算法吗？我怎么没找到呢？呵
我找的中国期刊全文数据库，有些关于钢筋的分割的论文，方便的话加我qq
147440973我给你发过去。
3＊3+5＊1=14
14=7+7
但7m*2的无论如何都分不出来3m*3和5m*1的
1、首先需将可用材料从小到大进行排序（能用小则不用大）；
2、再将目标从大到小排序（优先对大的目标进行匹配）；
3、0次切割优先于1次切割，1次切割优先于2次切割，依次类推.....（该推论可证明）
(1) 从小到大找出不需切割就能匹配目标的可用材料；
(2) 继续找出一次切割就能匹配目标的可用材料；即满足：Sk=Ti+Tj 的 S
....
4、对未能找到匹配的目标，需在剩余材料中进行切割
(1) 从小到大对可用材料尝试进行切割（优先匹配大的目标），切割下的部分必定不会与剩余目标匹配（或大或小）；
(2) 切割下的部分若比最小的目标大，则进入可用材料中，继续(1)；
(3) 若出现比最小目标小的边角料，这时需衡量是否需要进行拼接（可有不同的判断方法！）
示例：
可用材料 4m*3、6m*5、7m*5、8m*10、10m*8
目标 5m*3、4m*4、3m*3、1m*5
即：
可用 4 4 4 6 6 6 6 6 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 10 10 10 10 10 ...
目标 5 5 5 4 4 4 4 3 3 3 1 1 1 1 1
(1) 5 5 5 4 3 3 3 1 1 1 1 1 <4 4 4> 0次分割
(2) 1 1 <4 4 4 6=5+1 6=5+1 6=5+1 6=3+3 7=4+3> 1次分割
(3) 将6切割2次匹配 1 1
库:
如有 a b c d 四个长度.
基本长度组合情况, a, b, c, d, a+b, a+c, a+d, a+b+c, a+b+d, a+b+c+d, b+c, b+d ......
库存支数?
每切割一次后, 的新组合....客:
使用长度组合情况去对应现在库组合....