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 的大作中提到】
: 【 以下文字转载自 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
|
|
