Cod*_*key 14 optimization combinatorics
基本上,给定一个正的非零数字的排序列表,比如{1,4,5},更改列表中的单个数字以最大化可能的不同组合.以上给出了1,4,5,6,9,10,即六种组合.如果我们要改变4到2所以我们有{1,2,5},我们得到1,2,3,5,6,7,8,即7种组合.
我需要找到一个数字x来添加到列表的单个数字,以最大化组合的数量.x应该是最小的abslout值,我们可以加或减.
我通过枚举使用蛮力来完成它,它在指数时间内运行很多次.因此,对于较大的问题,这是不可行的.现在我需要快速完成.
只检查组合数是指数时间吗？我必须找到确切的最佳解决方案.
解决这个问题的关键词是什么？我试图找到一个重复,所以我可以使用动态编程和某种分支和绑定来限制爆炸,但它是没用的.
这只是一个尝试，我没有编写任何代码，甚至没有对此进行任何证明。
由于您只能更改一个值，因此我认为消除组合的最简单方法（我知道您不想这样做，但听我说完）是使两个数字相加为另一个数字列表。所以在你的例子中，1 4 5因为1 + 4 = 5你失去了那里的组合。因此，我将对数字集进行查询，以了解哪些数字对会产生该集的另一个成员。这是O(n^2 lg n)因为您将每个数字与其他每个数字进行比较，并且在此过程中还搜索（排序的）数字列表以查找它是否存在。
您的候选人是“冲突”次数最多的候选人。毫无疑问，通过将最容易发生碰撞的数字设为零碰撞数字，您将获得最终结果的最大增加。从那里开始，只需找到要添加/减去什么数字以使其成为非冲突数字即可。我还没有找到正确的方法来做到这一点，但我怀疑它可以通过动态编程在多项式时间内完成。
还有一个严重的问题，就是你们之间有联系。我认为这在最坏的情况下会增加*n你的复杂性，因为你最多只能n同时进行搜索。因此，假设您可以及时计算上述问题，n^p其中 p 是某个常数多项式，那么整个问题仍然可以及时解决n^(p+1)。
这无疑是一个棘手的问题，我希望这篇文章能够对这个问题有所启发。两个月后，总得有人来尝试吧？:)