|
|
发表于 2023-10-2 17:00:21
|
显示全部楼层
搜索不等同于去穷举。
实际上对于这个题目，搜索解的过程中，有很多技巧可以用。
i)我们可以用部分和进行剪枝:
比如搜索过程中前面两个数分别选择了1/2+1/3,那么第三个数必然小于1/6,我们可以从1/7开始，同样，如果第三个数选择了1/7,那么第四个数必然小于1/42,我们可以从1/43开始等等。
同样，如果我们发现当前搜索过程导致将所有余下数中最大的若干个添加进去都达不大1,那么自然也可以停止搜索。
对于这个部分，我们可以事先计算好数组max_sum[key][num]
保存所有分母不小key的情况下,num个数字和的最大值。
另外还可以事先计算min_sum[num],保存num个数字和的最小值，如果已经添加了16-num个数字，和超过了1-min_sum[num],那么也可以裁减掉。
ii)我们可以事先过虑掉一些不可能的情况，从而提高搜索效率。
比如很显然，所有大于128的素数的倒数不可能参与，可以事先淘汰掉，不参与搜索。
更加进一步分析，可以发现所有分母包含大于85的素因子的数都不能够参与。
进一步分析应该还可以过虑掉更多素因子。
iii)对于部分大素数，还有一些限制可以使用，比如对于某个较大的素数p
在256之内，可以参与的p的倍数对应的项有$1/p,1/(2p),...,1/(kp)$等
对于p比较大时，k会比较小，那么对于$k!(x_1/p+x_2/(2p)+...+x_k/(kp))$其中$x_1,x_2,...,x_k$分别为0和1
我们只关心这一项是整数的情况，上面总共有$2^k$种情况，但是整数的情况比例会比较低(大概$1/p$),在k不是特别大时，我们通过这种方法可以得到一些比较有用的模板，对于所有分母为p的倍数的情况，总共就只能几个模板情况可用。 |
|
发表于 2023-10-2 16:57:00
