给定 N 个整数区间 [lo_i,hi_i]。
从每个间隔中选择一个数字,使得它们的按位或成为给定数字 X。(结果是否比 X 多 1 位并不重要;即如果生成的数字是 Y,(X&Y)==X应该持有)
最佳答案
我猜这个问题是 NP 完全的,尽管我还没有发现一个 NP 难题可以很容易地归结为这个问题。
但是对于那些包含 2^(mostSignificantDigit) - 1 的集合,我会做一个启发式的:首先,尝试数字 1...1
(mostSignificantDigit-1 个),其次具有最高有效位和尽可能多的其他位的数字。这种启发式方法仅在您需要一组具有最高有效位和一些不同的较低有效位的数字的情况下才不好。
通过这种启发式,您还可以在这些集合中选择最大的数字 1....1 作为进一步的启发式。
关于algorithm - 通过按位或生成想要的数字,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9497845/