高难度算法征解，分不够再加 (新帖)
最近公司有一个关于自动配料方面的软件，由小弟接手，关于算法部分苦思不得其解，望各位大哥大姐赐教。具体如下：
假设：
库存中有4m*3、6.5m*5、7m*5、8m*10、10m*8(4m*3表示4米的材料有3根)，
现在用户需要3m*3、3.5m*1、4m*4、5m*3。
问用户该怎么取材，才能使浪费余料最少、材料的切割次数最少？
本题优先级是：
1、浪费余料最少(优先级最高)。
2、切割次数最少。
可以认为库存里最长的材料肯定比用户需要的最长的材料长。
浪费余料：就是在本次切割过程中，切割下来的，但没有用在本次用户要求上的材料都算浪费余料
[解决办法]
对于我来说难了
一点头绪没有
帮顶
[解决办法]
问一下，如果10m长的材料切割成二段5m长的，是否这两段都算合格可用的材料？
[解决办法]
如果是实际应用的话
这些材料的规格 （包括库存和用户需求的材料）应该有更多的限制吧
如果材料规格和需求规格完全随机 那我是没什么办法了...
关注&帮顶...
[解决办法]
小弟拙见
写一函数
第一步 在客户要求中的每一项和库存作比较 如：客户要3m*2 在库存中找正好3M的有就在客户要求和库存中减去客户的要的数量如果库存不购那就库存有多少出多少 然后修改客户需求 递归本函数 如客户要3m*2 库存中有 3m*1 那经过这一步之后 库存为0 客户要求变3m*1
第二步 在库存中查找有没有是客户要求材料整数倍的 如客户要3m*2 库存中有6m*4的 记录一次切割 修改库存和客户要求 递归本函数
第三步 在客户要求中任意个材料相加后的长度等于库存中一个材料的长度 如客要求 3m*3 2.5*2 库存中 有个5.5 的 记录切割 修改 递归函数
第四步 客户要求中的单个材料个数相乘再加任意另一个或几个材料 等于仓库中的材料 如 2m*2 3.5*1 库存中正好有一格7.5的 记录两次切割 修改 递归
[解决办法]
帮顶
[解决办法]
这题好象在数据库版 见发过了~
[解决办法]
个人想法：
1。以客户规格组合查找匹配倍数的库存规格，以组合中数量小的为标准减库存数、需求数，循环处理（可根据实际是优先短的还是优先长的做组合）
2。无完全匹配的库存规格，以单客户规格最大倍数规格（如5M客户规格可找到相似的6.5M--1倍和10M--2倍的库存规格，取最大倍数规格）循环减库存数、需求数
[解决办法]
取10m 1根、8m 1根、7m 1根、6.5m 1根、4m 3根
10m*1 -> 5m*2
8m*1 -> 5m*1,3m*1
7m*1 -> 4m*1,3m*1
6.5m*1 -> 3.5m*1,3m*1
4m*3 -> 4m*3
得到5m*3,4m*4,3.5m*1,3m*3
浪费0m，切割4次
[解决办法]
楼上的够行啊
但若是一般情况呢
比如没有8M的
[解决办法]
我认为应该先将厂里的每一种材料能可能切好的客户的每一种材料算出来
然后一一枚举 进行比较
大约比较去年100次就行了吧
[解决办法]
自己的帖子自己回，自己的分自己拿
