optimization - 最大化整数和的组合数

Question

基本上，给定一个非零正数的排序列表，例如 {1, 4, 5}，更改列表中的单个数字以最大化可能的不同组合。以上给出
1、4、5、6、9、10，即六种组合。如果我们将 4 更改为 2，得到 {1, 2, 5}，我们将得到 1, 2, 3, 5, 6, 7, 8，即七种组合。

我需要找到一个数字 x 添加到列表的单个数字中以最大化组合数量。 x 应该是最小的绝对值，我们既可以加也可以减。

我已经通过枚举使用蛮力完成了它，它在许多倍指数时间内运行。所以对于较大的问题是不可行的。现在我需要快速完成。

仅检查组合的数量是指数时间吗？我必须找到确切的最佳解决方案。

解决这个问题的关键词是什么？我试图找到一个复发，所以我可以使用动态编程和某种分支来限制爆炸，但这没有用。

我研究过 cutting mill 等问题, subset sum ，以及很多其他的组合优化问题，看看我是否能找到一些想法。但我不明白。简单地验证解决方案是指数时间。

Answer 1

这只是一个尝试，我没有编写任何代码，甚至没有对其进行任何证明。

由于您仅限于更改一个值，因此我认为消除组合的最简单方法(我知道您并没有尝试这样做，但请听我说)是将两个数字相加到另一个数字列表。所以在你的例子中1 4 5因为1 + 4 = 5你会输掉那里的组合。因此，我将对一组数字进行查询，以了解哪些数字对会导致该组的另一个成员。这是O(n^2 lg n)当您将每个数字与其他数字进行比较时，同时搜索(排序的)数字列表以查找它是否存在。

您的候选人是“冲突”次数最多的候选人。毫无疑问，通过将最容易发生碰撞的数字设为零碰撞数，您将获得最大的最终结果增加。从那里，只需找到要添加/减去的数字以使其成为非冲突数字。我还没有找到正确的方法来做到这一点，但我怀疑它可以通过多项式时间内的动态规划来完成。

还有另一个严重的问题，你有关系。我认为这是在最坏的情况下添加一个额外的 *n根据您的复杂性，您最多可以有 n关系同时搜索。所以假设你可以在n^p中计算上述问题p 是某个常数多项式的时间，那么整个问题应该仍然可以在 n^(p+1) 中解决时间。

这肯定是一个问题，我希望这能够阐明它。两个月后，总得有人试一试吧？ :)