arrays - 最小化代表性整数的误差总和

Question

给定n个介于[0,10000]之间的整数作为D₁,D₂...,D_n，其中可能有重复，并且 n 可以很大:

我想在 [0,10000] 之间找到 k 个不同的代表性整数(例如 k=5)作为 R₁,R₂,...,R _k，所以所有代表整数的误差之和最小。

代表性整数的误差定义如下:

假设我们有 k 个代表整数，按升序排列为 {R₁,R₂...,R_k}，错误的 R_i是 :

我想最小化 k 个代表整数的误差总和:

如何才能有效地做到这一点？

EDIT1: k 个代表整数中最小的必须是最小的数{D₁,D₂...,D_n}

EDIT2: k个代表整数中最大的一定是{D₁,D₂...,D中最大的数_n}加1。比如当{D₁,D₂...,D_{n } 是 9787 那么 Rk 是 9788.}

EDIT3:一个具体的例子在这里:

D={1,3,3,7,8,14,14,14,30} 并且如果 k=5 并且 R 被选为 {1,6,10,17,31} 那么误差总和是:

误差总和=(1-1)+(3-1)*2+(7-6)+(8-6)+(14-10)*3+(30-17)=32

这是因为 1<=1,3,3<6 , 6<=7,8<10, 10<=14,14,14<17, 17<=30<31

Answer 1

尽管在社区的帮助下，您还是设法说明了您的数学上可以理解的形式的问题，你仍然这样做没有提供足够的信息使我(或其他任何人)能够提供你是一个明确的答案(我会把它作为评论发布，但是出于某种原因，我没有看到“添加评论”选项可用于我)。为了很好地回答这个问题，我们需要知道n 和 k 相对于彼此的相对大小以及 10000(或D_i 的预期最大值(如果它不是 10000)，以及是否达到确切的最小值至关重要(即使这需要大量的时间来计算)或者如果一个近似值也可以(如果是这样，你有多接近需要得到)。另外，为了知道运行的是什么算法最少的时间，我们需要了解什么样的硬件将运行算法(即，我们有 m 个 CPU并行运行的内核以及 m 相对于 k 的大小是多少)。

另一个重要的信息是这个问题是否会只解决一次，或者必须解决多次但存在整数 D_i 的分布之间存在某种联系从一个问题到下一个问题(例如，整数D_i 都是来自特定的、不变的随机样本概率分布，或者也许每个连续的问题都有它的输入是一个不断增加的集合，它是前一个集合问题加上一个额外的 s 个整数)。

您的问题没有合理的算法应该及时运行在某种程度上取决于 n 的线性关系，因为构建直方图n 个整数 D_i 需要 O(n) 时间，而答案优化问题本身只依赖于直方图整数而不是它们的顺序。没有算法可以及时运行小于 O(n)，因为这是问题输入的大小。

对所有可能性的强力搜索需要，(假设至少有一个 D_i 是 0 而另一个是 10000)，因为小 k，比如 k < 10，大约 O(10000^k-2) 时间，所以如果log₁₀(n) >> 4(k-2)，这是最优算法(因为在在这种情况下，暴力搜索的时间与读取输入的时间)。同样有趣的是，如果 k 是非常接近 10000，那么暴力搜索只需要O(10000^10002-k)(因为我们可以搜索不用作代表性整数的整数)。

如果您用更多信息更新问题的定义，我将依次尝试编辑我的答案。