s**x
发帖数: 7506 | 1 6.一条直线上有N个站台，已知任何两点间直达列车的票价，求出从起点到终点的票价
最优的乘车方案。因为从A到B，再从B到C的价格可能比直接从A到C便宜
7.N个job，要求分配到M台机器上，每个机器可以被分配0-N个job，但有些job相互排斥
不能被放到一起执行，给出所有可能的分配方案
怎么弄啊？多谢指点。 |
a********m
发帖数: 15480 | 2 6是最短路径。普通算法是地基丝特拉啥的那个算法。如果有一些额外信息还有个a*算
法。 |
s**x
发帖数: 7506 | 3 恩，可是复杂度很高， 因为每两个点都相连。
【在 a********m 的大作中提到】
: 6是最短路径。普通算法是地基丝特拉啥的那个算法。如果有一些额外信息还有个a*算
: 法。
|
l*********b
发帖数: 1541 | |
a********m
发帖数: 15480 | 5 还好。每个点处理一次。添加的时候需要排序.总时间应该小于nlgn
【在 s**x 的大作中提到】
: 恩，可是复杂度很高， 因为每两个点都相连。
|
g***s
发帖数: 3811 | 6 1是DP。因为是单向图，没有必要dijistra，Flyod就更没有必要了。 |
b*******8
发帖数: 37364 | 7 #6主体DP代码大概如下吧（未测试）
//0~N-1
min[0][0] = 0;
for (int i=1; i
min[0][i] = MAX_INT;
for (int i=1; i
for (int j=0; j
if (min[0][i] < min[0][j] + dist[j][i]) {
min[0][i] = min[0][j] + dist[j][i];
last[i] = j; //last[] 用来回溯路径
} |
b*******8
发帖数: 37364 | 8 7用类似8皇后的方法
N个job，要求分配到M台机器上，每个机器可以被分配0-N个job，但有些job相互排斥不能被放到一起执行，给出所有可能的分配方案
void matchJob(int N,int M,int level,int match[])
{
if (level == N) print match[] information;
else
for (int j=1; j <= M; ++j)
if (putting the job in jth machine causes no collision) {
match[level] = j;
matchJob(N, M, level+1, match);
}
}
void main()
{
...
matchJob(N, M, 0, match);
...
} |
d*******l
发帖数: 338 | 9 我觉得这是有问题的。一个小问题是if后面应该判断大于等于。另外逻辑上也有漏洞，
站点0和1之间的最短距离只在第一次循环中做了检查，只检查了经过站点0的情况，也
就是无论如何min[0][1]都等于dist[0][1]，这肯定是有问题的。
【在 b*******8 的大作中提到】
: #6主体DP代码大概如下吧（未测试）
: //0~N-1
: min[0][0] = 0;
: for (int i=1; i: min[0][i] = MAX_INT;
: for (int i=1; i: for (int j=0; j: if (min[0][i] < min[0][j] + dist[j][i]) {
: min[0][i] = min[0][j] + dist[j][i];
: last[i] = j; //last[] 用来回溯路径
|
s**x
发帖数: 7506 | 10
This is O(N2).
我觉得 first get the min distance from n1 to all the other points, say ni,
then get the min distance from ni to all othe n-I points, till the last
point, this is O(N2) too. Very simple.
【在 b*******8 的大作中提到】
: #6主体DP代码大概如下吧（未测试）
: //0~N-1
: min[0][0] = 0;
: for (int i=1; i: min[0][i] = MAX_INT;
: for (int i=1; i: for (int j=0; j: if (min[0][i] < min[0][j] + dist[j][i]) {
: min[0][i] = min[0][j] + dist[j][i];
: last[i] = j; //last[] 用来回溯路径
|
|
|
d*******l
发帖数: 338 | 11 从n1到所有其它点的最短路径不就是典型的单源最短路径问题么。。求出这个了问题也
就解决了
【在 s**x 的大作中提到】
:
: This is O(N2).
: 我觉得 first get the min distance from n1 to all the other points, say ni,
: then get the min distance from ni to all othe n-I points, till the last
: point, this is O(N2) too. Very simple.
|
a********m
发帖数: 15480 | 12 dijistra可以是nlgn或者n2(连接多的话)， dp是什么复杂度？ 另外感觉dj算法和dp思
想很象。
【在 g***s 的大作中提到】
: 1是DP。因为是单向图，没有必要dijistra，Flyod就更没有必要了。
|
s*****y
发帖数: 897 | 13 恩，同感。
【在 a********m 的大作中提到】
: dijistra可以是nlgn或者n2(连接多的话)， dp是什么复杂度？ 另外感觉dj算法和dp思
: 想很象。
|
s*****y
发帖数: 897 | 14 直线单向站台，难道min[0][1]不就是dist[0][1]?
不过也可能
a - > b-> c-> d
a->c->b 比a->b 便宜？
这也太变态了。
【在 d*******l 的大作中提到】
: 我觉得这是有问题的。一个小问题是if后面应该判断大于等于。另外逻辑上也有漏洞，
: 站点0和1之间的最短距离只在第一次循环中做了检查，只检查了经过站点0的情况，也
: 就是无论如何min[0][1]都等于dist[0][1]，这肯定是有问题的。
|
d*******l
发帖数: 338 | 15 所谓最短距离并不一定真的是距离，这题里是票价。题目里有这么一句：
“因为从A到B，再从B到C的价格可能比直接从A到C便宜“
【在 s*****y 的大作中提到】
: 直线单向站台，难道min[0][1]不就是dist[0][1]?
: 不过也可能
: a - > b-> c-> d
: a->c->b 比a->b 便宜？
: 这也太变态了。
|
s*****y
发帖数: 897 | 16 恩，但是这里的a b c我理解仍然是a->b->c，所以这也是make sense的
但是要站台是a-b->c
搭车从a到b的钱比从a搭到c，再往回搭回去b 贵，似乎不是很make sense。
【在 d*******l 的大作中提到】
: 所谓最短距离并不一定真的是距离，这题里是票价。题目里有这么一句：
: “因为从A到B，再从B到C的价格可能比直接从A到C便宜“
|
d*******l
发帖数: 338 | 17 这倒是，如果距离远的一定比距离近的贵，那上面的代码应该就是对的了。但题目本身
并没有清楚的给出这个限制。令人疑惑。
【在 s*****y 的大作中提到】
: 恩，但是这里的a b c我理解仍然是a->b->c，所以这也是make sense的
: 但是要站台是a-b->c
: 搭车从a到b的钱比从a搭到c，再往回搭回去b 贵，似乎不是很make sense。
|
k****n
发帖数: 369 | |
C***U
发帖数: 2406 | 19 my guess
dynamic programming or greedy method
【在 s**x 的大作中提到】
: 6.一条直线上有N个站台，已知任何两点间直达列车的票价，求出从起点到终点的票价
: 最优的乘车方案。因为从A到B，再从B到C的价格可能比直接从A到C便宜
: 7.N个job，要求分配到M台机器上，每个机器可以被分配0-N个job，但有些job相互排斥
: 不能被放到一起执行，给出所有可能的分配方案
: 怎么弄啊？多谢指点。
|
b*******8
发帖数: 37364 | 20 如果dist[1][2]可能大于13再32，那貌似只能Dijistra，把此图看成一个N个顶点的完
全图，然后找0到N的最短路径。算法就不用写了，标准方法。 |
|
|
s*****y
发帖数: 897 | 21 en. Agree.
【在 b*******8 的大作中提到】
: 如果dist[1][2]可能大于13再32，那貌似只能Dijistra，把此图看成一个N个顶点的完
: 全图，然后找0到N的最短路径。算法就不用写了，标准方法。
|
g***s
发帖数: 3811 | 22 dijkstra用在这题也是n^2.
这题我的理解是，做车还是从起点到终点，不换车，但通过买不同间段的票来达到最优。
如果可以往回坐，其实就完全是dijkstra的原题了，看不出考点。而这个不换车的考点
是，你要理解了dijkstra后如何写一个简版的DP算法。
【在 a********m 的大作中提到】
: dijistra可以是nlgn或者n2(连接多的话)， dp是什么复杂度？ 另外感觉dj算法和dp思
: 想很象。
|
l******n
发帖数: 492 | 23 动态规划
【在 s**x 的大作中提到】
: 6.一条直线上有N个站台，已知任何两点间直达列车的票价，求出从起点到终点的票价
: 最优的乘车方案。因为从A到B，再从B到C的价格可能比直接从A到C便宜
: 7.N个job，要求分配到M台机器上，每个机器可以被分配0-N个job，但有些job相互排斥
: 不能被放到一起执行，给出所有可能的分配方案
: 怎么弄啊？多谢指点。
|
l******n
发帖数: 492 | 24 n个最小值的和不一定小于直达的
【在 s**x 的大作中提到】
:
: This is O(N2).
: 我觉得 first get the min distance from n1 to all the other points, say ni,
: then get the min distance from ni to all othe n-I points, till the last
: point, this is O(N2) too. Very simple.
|
P**********c
发帖数: 3417 | 25 这个不对吧。
【在 s**x 的大作中提到】
:
: This is O(N2).
: 我觉得 first get the min distance from n1 to all the other points, say ni,
: then get the min distance from ni to all othe n-I points, till the last
: point, this is O(N2) too. Very simple.
|
P**********c
发帖数: 3417 | 26 从题目的意思看，应该不可以往回坐。
优。
【在 g***s 的大作中提到】
: dijkstra用在这题也是n^2.
: 这题我的理解是，做车还是从起点到终点，不换车，但通过买不同间段的票来达到最优。
: 如果可以往回坐，其实就完全是dijkstra的原题了，看不出考点。而这个不换车的考点
: 是，你要理解了dijkstra后如何写一个简版的DP算法。
|
s*****n
发帖数: 5488 | 27 那就等于DAG的shortest path去掉topological sorting 那一步。
O(V+E)
【在 P**********c 的大作中提到】
: 从题目的意思看，应该不可以往回坐。
:
: 优。
|
P**********c
发帖数: 3417 | 28 这个有O(n^2)个edge, 所以这个思路没什么帮助，code也不好写。
【在 s*****n 的大作中提到】
: 那就等于DAG的shortest path去掉topological sorting 那一步。
: O(V+E)
|
