发布于 2012-12-21 14:54:16
27楼
这个问题很复杂,除了遍历,没有一种策略能肯定找出最优解,但所幸的是我们不需要最优解,只要合格即可。
记录20个工件的偏差值为正或负,将它们排序,需要取出15个和值在50以内的数
平均允许的误差是正负3.3克
1、最理想,每个工件的误差都3.3克以内,随便取15个即可
2、标记出两端超过3.3克的误差序号,如果中间能凑足15个(或者说两端不超过5个),得到合格解(随机原理,这种可能性应该是比较大的)
3、两端超过5个,先将中间加起来,看总误差正负,根据正负反向从两端去试加,如果能加到15个满足要求,得到合格解
4、最复杂的情况,到了第3步仍然得不出合格解
这种就是上面提到的各种方法去拼凑了
事实上,我们还可以继续上面的策略,比如中间有12个在平均误差内,累计误差是+30,剩下的挑不出两个合格的了。剩下的7选3,允许的误差是[-80, +20],标记两端误差范围是[-26.6, 6.6],这样可以重复前面的步骤。
但这个仍有可能漏解,因为我们留下的12个是连续排列的,可能这12个不在任一个合格解内,所以后面也不可能得到合格解。这种情况有两个策略来试,一个只取中间8-10个,让剩下的多一点,另一种情况是随机取8-10个。
这样试下来,漏解的可能会控制在一定的范围内,不行就报警人工挑捡了,反正生产也会出现遍历也没有合格解的情况,我们的策略只要控制漏解率在一定范围内,是可以接受的。
另外:C(20,15)和C(20,5)在数学上只是排列数一样,但在这个具体问题中,是完全不同的。
生命存在的方式只有两种:腐烂或燃烧