还是靠VBA来帮我计算最少用你多少根棍子吧

小倒霉蛋子 · 发表于 2012-9-14 14:05

pp9257 发表于 2012-9-14 11:09
我觉得代码是算法过于简单，很多情况都没考虑到的。。
明显的举例
1250 10

是的

当有类似
1200
700
600
200

这种时候只会考虑1200以后可以截一个700，而不会考虑 1200之后 600+200这种更适合的情况

小倒霉蛋子 · 发表于 2012-9-14 14:08

pp9257 发表于 2012-9-14 11:09
我觉得代码是算法过于简单，很多情况都没考虑到的。。
明显的举例
1250 10

但是不会出现你说的应该是79但是计算出来的是77的情况
应该是77计算出来是79倒是有可能

840205910 · 发表于 2012-9-14 14:15

小倒霉蛋子发表于 2012-9-14 14:08
但是不会出现你说的应该是79但是计算出来的是77的情况
应该是77计算出来是79倒是有可能

你好：for ii = 1 to numbr2
next ii
起到的作用是什么，限制循环的次数？

小倒霉蛋子 · 发表于 2012-9-14 14:25

840205910 发表于 2012-9-14 14:15
你好：for ii = 1 to numbr2
next ii
起到的作用是什么，限制循环的次数？

myNum2 是之前计算的剩余材料还能截的取需要长度的数目

for ii = 1 to myunm2
next ii
之间的这段代码是为了避免截取的数目超过需要的数目

举例说明：
还剩800的材料，需要的长度是400，还需要1个
那么，就通过这段代码只截取一个400而不要更多

veggieg · 发表于 2012-9-14 15:02

小倒霉蛋子发表于 2012-9-14 10:03

高人啊！！！请问能讲解一下这个算法的数学原理吗？

小倒霉蛋子 · 发表于 2012-9-14 15:17

本帖最后由小倒霉蛋子于 2012-9-14 15:21 编辑

veggieg 发表于 2012-9-14 15:02
高人啊！！！请问能讲解一下这个算法的数学原理吗？

简单地说，一根2000的材料，按需要长度由长到短的判断是否需要截取，需要截取的话能否截取，可以截取的话可以截取多少根，每截取一根计算一次
比如第一根材料：2000，先判断是否需要截取1500的，那么1500的还需要10个，并且2000的材料还能截取1个1500的，所以我们从2000里面减去1500，同时从1500需要的10里减去1。
这时材料还剩下500，我们判断是否需要截取800，答案是需要，再判断能否截取800,500<800不能截取
那么我们继续判断是否需要700的，和800结果一样，600和800的结果也是一样；
再判断450，需要截取并且剩余材料的500可以截取一个450，450需要的数目7里减去1,
剩余50，经判断无法截取200的，那么我们第一根材料就计算完成了

然后拿出第二根材料，进行新一轮的循环

不知道我这么说能让你理解么？

灰袍法师 · 发表于 2012-9-14 16:07

小倒霉蛋子发表于 2012-9-14 15:17
简单地说，一根2000的材料，按需要长度由长到短的判断是否需要截取，需要截取的话能否截取，可以截取的 ...

这样的算法，对很小规模的简单数据还可以
稍复杂一点就会算得很差劲的，如以下也是论坛发过的问题数据，最优解是194根6000长度的原料。
贪婪算法只能算出206
长度数量
1664 32
1599 96
1552 160
1409 16
1352 384
802 112
660 64

pp9257 · 发表于 2012-9-14 16:16

本帖最后由 pp9257 于 2012-9-14 16:17 编辑

灰袍法师发表于 2012-9-14 16:07
这样的算法，对很小规模的简单数据还可以
稍复杂一点就会算得很差劲的，如以下也是论坛发过的问题数据， ...

这个还是一维的就这么难，要是二维的，还了得

三维的呢。。

KCFONG · 发表于 2012-9-14 16:19

灰袍法师发表于 2012-9-14 16:07
这样的算法，对很小规模的简单数据还可以
稍复杂一点就会算得很差劲的，如以下也是论坛发过的问题数据， ...

有幸法师光临
请指导
让我们学习

灰袍法师 · 发表于 2012-9-14 16:36

KCFONG 发表于 2012-9-14 16:19
有幸法师光临
请指导
让我们学习

指导不敢当，我自己对这个问题暂时木有办法，都是拿 go nest 1d 算的
这个软件我在论坛也多次推荐了，又不贵，才2xx美刀而已。。。。。。
我目前能想到的做法，还是跟我以前求解这个帖的一样，生成利用率高的组合方案（这个等于一个极其简单的背包问题）
随机选这些方案，直到满足所有材料要求，计算耗材得分，重复N遍取最高分的一次。
下帖最优解是29根，是的，才29根就难的要命，关键是最优解的利用率很高。。。。。。
http://club.excelhome.net/thread-307533-1-1.html
方便大家，我直接把数据贴上来，原料长度是6300，无需考虑切口
2540 21
2230 13
1720 12
1670 5
1620 19
1400 7
1080 4
980 4
840 8
690 10
350 16
330 4
240 6

		自动登录	找回密码
密码			免费注册

[求助] 还是靠VBA来帮我计算最少用你多少根棍子吧

评分

评分