f*******h
发帖数: 43 | 1 设计一个pickup dispatching system。 二维矩阵表示地理区域，分布有M个乘客和N辆
车(M>>N)，假设乘客位置固定， 让设计一个算法，保证每辆车都拉到一个乘客，并且
所有的pickup所花费的路程和最小。
这道题看着像best meeting point， 不过又不太一样。 大家有什么思路吗？ | r********k
发帖数: 258 | 2 my feeling is there is no solution to find the answer. they may test you how
you approach the question, and work out a good enough solution. | b***s
发帖数: 117 | 3 这个需要问清楚有什么条件吧
不然不是就找到最近的乘客拉上吗？如果两辆车有冲突，就去找下一个最近的
有点MST的样子，但只是minimum spanning
可能解决冲突，得到最小的路程是难点，需要弄个 DP来
再具体点，我的想法就是有 车1 c1, 车2 c2, 对应人1 r1, 人2 r2, 人3 r3,
(c1, r1) = 1
(c1, r2) = 4
(c1, r3) = 7
(c2, r1) = 2
(c2, r2) = 7
(c2, r3) = 7
大家都是对人1最近，但是显然应该车1接人2,而车2去接人1 | k******a
发帖数: 44 | 4 这个题需要更多交流。
同一时间，一辆车只能pick一个客人?
每次计算，限制条件都是N辆车pickN个客人的最小COST，是这样么？
笨笨的思路:
1. 按照每辆车计算最近的TOP N candidates，按照距离排序
2. 按照最小距离排序所有车辆
3. 扫描每辆车的candidates并记录，如果candidate未assigned，assign， 如果已经
assigned， try next candidate
4. 如果某车所有candidates都被assigned, 放入set S
5. 如果处理结束S不为空，则重复1，2，3，4 | r*******y
发帖数: 270 | |
|
