p******m 发帖数: 154 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: peachgcm (peach), 信区: JobHunting
标 题: 欢迎大家积极讨论一个ms简单的算法面试题
发信站: BBS 未名空间站 (Sat Mar 20 19:30:47 2010, 美东)
在real line上给出n个数,找出k个数,such that the sum of squares of distances
is minimized。例如,assume c是
这k个数的几何zhongxin。c = (n1+...+nk)/k 。 Then 目标函数就是: (n1-
c)^2+...+(nk-c)^2 | s*x 发帖数: 3328 | 2 CS 那边不是已经有人给你回复了?你一个个测试,时间也就是线性的,这个结果已经
很好了。没办法得出更好结果的,因为涉及到 n 个数取 k 个数,变量取值是 0/1 不
是连续的,分析的方法用不上。
distances
【在 p******m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 【 以下文字转载自 JobHunting 讨论区 】 : 发信人: peachgcm (peach), 信区: JobHunting : 标 题: 欢迎大家积极讨论一个ms简单的算法面试题 : 发信站: BBS 未名空间站 (Sat Mar 20 19:30:47 2010, 美东) : 在real line上给出n个数,找出k个数,such that the sum of squares of distances : is minimized。例如,assume c是 : 这k个数的几何zhongxin。c = (n1+...+nk)/k 。 Then 目标函数就是: (n1- : c)^2+...+(nk-c)^2
|
|