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个任
|