我想要做的是不断向一个集合中添加更多的值,并尽量让它们彼此之间距离尽可能远。我相信肯定有几种算法可以解决这个问题,但我可能只是没有用正确的术语进行搜索。如果有人能指向一个解决方案(不需要特别高效),那就太棒了。
实际上,给定一个范围在Min-Max之间的值S集合,我需要计算出一个新值V,也在该范围内,使得V与S中所有值之间的距离之和最大化。
实际上,给定一个范围在Min-Max之间的值S集合,我需要计算出一个新值V,也在该范围内,使得V与S中所有值之间的距离之和最大化。
{1, 10, 10, 10, 10}
。通过将 V
插入到接近1而不是在1和10之间的中间位置(即5)来最大化距离的总和。我有什么遗漏吗? - Tim Biegeleisen`[1, 10, 10, 10, 10]` -> `[9, 0, 0, 0]` == `9`,
`[1, 1.5, 10, 10, 10, 10]` -> `[.5, 8.5, 0, 0, 0]` == `9`,
`[1, 1.00001, 10, 10, 10, 10]` -> `[.00001, 8.9999, 0, 0, 0]` == `9`,
`[1, 5, 10, 10, 10, 10]` -> `[4, 5, 0, 0, 0]` == `9`
- tophyrsumDistance()
,它接受一个新值V
和当前集合中的所有值,并输出V
与集合中每个值之间距离的总和。sumDistance()
的定义域d
,其中Min <= d <= Max
,并跟踪域中每个值V
的总和。当你遇到一个新的最大总和时,记录它。给你最大总和的V
值是你保留并添加到你的集合中的值。假设距离 d(a,b) = |a-b|
,那么min
和max
中的一个总是会产生最大值。
证明:
假设您有一个不在端点的V。那么你有n1
个低值和n2
个高值。最小值处的总距离至少会比最大值处的总距离大(n1 - n2) * (max - V)
,而最大值处的总距离至少会比最小值处的总距离大(n2 - n1) * (V - min)
。
由于n1 - n2
和n2 - n1
中至少有一个非负,因此最大值总是可以在端点之一找到。