最小化代表性整数的错误总和

Question

给定[0,10000]之间的n个整数作为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然后R _k是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 的相对大小（如果不是 10000，则为 D _i的预期最大值），以及是否重要你达到了精确的最小值（即使这需要大量的计算时间），或者如果接近近似也可以（如果是这样，你需要达到多接近）。此外，为了知道什么算法在最短的时间内运行，我们需要了解什么样的硬件将运行该算法（即，我们是否有 m 个 CPU 核心可以并行运行以及大小是多少） m 相对于 k)。

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

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

对所有可能性进行强力搜索需要（假设至少有一个 Di_为0，另一个为 10000），对于较小的 k，例如 k < 10，大约需要 O(10000 ^k-2 ) 时间，因此如果log ₁₀ (n) >> 4(k-2)，这是最佳算法（因为在这种情况下，暴力搜索的时间与读取输入的时间相比是微不足道的）。值得注意的是，如果 k 非常接近 10000，那么强力搜索只需要 O(10000 ^10002-k ) （因为我们可以搜索不用作代表性整数的整数）。

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