P*******b
发帖数: 1001 | 1 第二题给你3个任务T1, T2, T3， 每个任务需要的单位labor不一样，比如T1需要8个
units，T2只要4个units （反正数字他随机给）。 有3个人， P1, P2, P3， 每个人每
天能完成的单位labor也不一样， 比如P1一天可以做5个unit，P2一天只能做3个unit。
限制是，一个人在一天之内只能做一个task，但是可以几个人做同一个task。问如何
schedule，三个任务完成的时间最短。因为数字随机给， 所以我觉得他自己未必就知
道正确的答案。反正你大概分一下，不要有明显的bottleneck，给他一个答案就可以了
。他的重点不在这里。接下来他就问，如果不考虑具体的数字，给你3个任务 3个人，
问你一共有多少种assignments。任务的先后顺序matter。然后这个问完，只要你给的
答案比较大（我后来想想，好像我的答案少了，。。。）他就不会追着你问具体的数字
了。他就会说，就这样一个简单的scenario，就有这么多种可能， 那我如果有500个任
务， 1000个人会有多少种assignment 可能性。我说这个会是一个很大很大的数， 他
就说如果是那样，就没有可能说先把所有可能都列出来，然后验证哪个最优， 那你要
怎么办。随便扯了一下divide&conquer，dynamic programming，时间也差不多了，就
到此打住。 |
h**6
发帖数: 4160 | |
P********l
发帖数: 452 | 3 觉得这道题更象在考楼主的人品，除非楼主就是搞这个的。google一下real time
system scheduling。从第一道题开始，可以延伸到很多优化技术。不要信口开河就好
。 |
P********l
发帖数: 452 | 4 Huangarian algorithm比较老了，网上有现成代码。有更新的算法。
【在 h**6 的大作中提到】
: http://en.wikipedia.org/wiki/Assignment_problem
: http://en.wikipedia.org/wiki/Hungarian_algorithm
: 我觉得匈牙利算法太繁琐了，这题可能还是在考排列组合，能答出有多少种方法就足够了。
|
s*****n
发帖数: 5488 | 5 花了5分钟想了一下多少种assignment.
假设P都是slave.每天都要work, like us.则，对于 T进行标记p1, p2, etc.
则for every day 组合数位C^N(P)^(T)。
summing up until for all SUM(labor(T)) <= sum(sum labor(p) on T)
这应该是一个uppbound.
考我这道题估计当场要挂掉了。
【在 P*******b 的大作中提到】
: 第二题给你3个任务T1, T2, T3， 每个任务需要的单位labor不一样，比如T1需要8个
: units，T2只要4个units （反正数字他随机给）。 有3个人， P1, P2, P3， 每个人每
: 天能完成的单位labor也不一样， 比如P1一天可以做5个unit，P2一天只能做3个unit。
: 限制是，一个人在一天之内只能做一个task，但是可以几个人做同一个task。问如何
: schedule，三个任务完成的时间最短。因为数字随机给， 所以我觉得他自己未必就知
: 道正确的答案。反正你大概分一下，不要有明显的bottleneck，给他一个答案就可以了
: 。他的重点不在这里。接下来他就问，如果不考虑具体的数字，给你3个任务 3个人，
: 问你一共有多少种assignments。任务的先后顺序matter。然后这个问完，只要你给的
: 答案比较大（我后来想想，好像我的答案少了，。。。）他就不会追着你问具体的数字
: 了。他就会说，就这样一个简单的scenario，就有这么多种可能， 那我如果有500个任
|
s*****n
发帖数: 5488 | 6 not sure iti is an assignment. at least it is sequence of assignment, and we
need global optimization.
够了。
【在 h**6 的大作中提到】
: http://en.wikipedia.org/wiki/Assignment_problem
: http://en.wikipedia.org/wiki/Hungarian_algorithm
: 我觉得匈牙利算法太繁琐了，这题可能还是在考排列组合，能答出有多少种方法就足够了。
|
s*****n
发帖数: 5488 | 7 又想了一下，我觉得我要是回答就先做出个BFS的naive solution.然后要hint是不是np
complet or higher. 如果是，用A*加strategy。如果不是那么试图建立一个lemma,
建立recusive框架，最后如果是dp建立suboptimal structure.
尽量show一下把。如果这道题是linear programming的话，只好认了。当年
写匈牙利算法，花了一个星期才通，n年过去了，全都交出去了。
【在 P*******b 的大作中提到】
: 第二题给你3个任务T1, T2, T3， 每个任务需要的单位labor不一样，比如T1需要8个
: units，T2只要4个units （反正数字他随机给）。 有3个人， P1, P2, P3， 每个人每
: 天能完成的单位labor也不一样， 比如P1一天可以做5个unit，P2一天只能做3个unit。
: 限制是，一个人在一天之内只能做一个task，但是可以几个人做同一个task。问如何
: schedule，三个任务完成的时间最短。因为数字随机给， 所以我觉得他自己未必就知
: 道正确的答案。反正你大概分一下，不要有明显的bottleneck，给他一个答案就可以了
: 。他的重点不在这里。接下来他就问，如果不考虑具体的数字，给你3个任务 3个人，
: 问你一共有多少种assignments。任务的先后顺序matter。然后这个问完，只要你给的
: 答案比较大（我后来想想，好像我的答案少了，。。。）他就不会追着你问具体的数字
: 了。他就会说，就这样一个简单的scenario，就有这么多种可能， 那我如果有500个任
|
