p**********e
发帖数: 316 | 1 http://www.mitbbs.com/article_t/JobHunting/32281037.html
一个二维数组代表了城市中的坐标，给定N个人的坐标，求坐标使所有人
走到这个坐标的距离的和最小，只可以横着或者竖着走，不可以斜着走
更一般性的问题是找一个地方建distribution center,如何选址
另一个问题
given an array of strings, 求max len(A)*len(B), A B have no common character
一个貌似很简单的问题，
给定两个array of integers, the same size, 两两配对, 求绝对值之和最小
http://mattcb.blogspot.com/2013/03/minimum-weight-of-two-groups
没看懂解法 | s**x
发帖数: 7506 | 2 第一题好像以前讨论过。
一维的情况， one point, it is the point, 2 points, any point between the
two points should work, 3 points, should be the middle point.
so it should be the median point.
2D, X Y direction should be independent, so it is just to find the median
for all numbers in X Y direction separately. | x*****0
发帖数: 452 | | M***A
发帖数: 5 | 4 顶
最后那题我觉得那个blog给出的答案把问题复杂化了。大概他是想考虑可以重复选某个
数的情况。比如只选b1，出现(a1, b1), (a2, b1), (a3, b1)三个pair。
其实我觉得没必要，只要排序然后计算sum|ai - bi|就可以了。
【在 p**********e 的大作中提到】
: http://www.mitbbs.com/article_t/JobHunting/32281037.html
: 一个二维数组代表了城市中的坐标，给定N个人的坐标，求坐标使所有人
: 走到这个坐标的距离的和最小，只可以横着或者竖着走，不可以斜着走
: 更一般性的问题是找一个地方建distribution center,如何选址
: 另一个问题
: given an array of strings, 求max len(A)*len(B), A B have no common character
: 一个貌似很简单的问题，
: 给定两个array of integers, the same size, 两两配对, 求绝对值之和最小
: http://mattcb.blogspot.com/2013/03/minimum-weight-of-two-groups
: 没看懂解法
| h*****u
发帖数: 109 | 5 我感觉这个是one-to-all shortest path的变形。如果在坐标上有一个点s，距离的和
最小，等同于每个城市到s的shortest distance。
for s in all points
determine the sum of the shortest distances
output the minimum one
算shortest distances时，可以用all-pair shortest paths, such as Floyd-
Warshall | h*****u
发帖数: 109 | 6 A[]={5,3,4};
B[]={1,6,2};
min = 5
3-1, 4-2,5-6
这个是assignment problem的应用。
首先
for i in A
for j in B
compute the abs(i,j)
abs 用作在objective里。然后就是assignment problem.
如何解assignment, 可以看看Kuhn的Hungarian_algorithm
http://en.wikipedia.org/wiki/Hungarian_algorithm | g*****g
发帖数: 212 | 7 blog那个解法貌似是错的。。。
character
【在 p**********e 的大作中提到】
: http://www.mitbbs.com/article_t/JobHunting/32281037.html
: 一个二维数组代表了城市中的坐标，给定N个人的坐标，求坐标使所有人
: 走到这个坐标的距离的和最小，只可以横着或者竖着走，不可以斜着走
: 更一般性的问题是找一个地方建distribution center,如何选址
: 另一个问题
: given an array of strings, 求max len(A)*len(B), A B have no common character
: 一个貌似很简单的问题，
: 给定两个array of integers, the same size, 两两配对, 求绝对值之和最小
: http://mattcb.blogspot.com/2013/03/minimum-weight-of-two-groups
: 没看懂解法
| h*****u
发帖数: 109 | 8 如果没有障碍物，这题应该不用求shortest path. 可以直接用weighted median, 先是
X, 然后Y. 可以看CLRS order statistics的习题。网上有答案。 | p******e
发帖数: 14 | |
|
