c*********t 发帖数: 1861 | 1 Solution 见楼底。。。
这次N 个 WSN 因为已经脑残了,所以相约劳动节去绣花 。。。好了,废话就不说了,大家帮我想这个题:
不同的 WSN 绣不同的款式需要的时间不一样。如果我们把 WSN # i 绣 j 款式需要的时间记做 T(i,j), 那么,T(i,j)组成了一个 N by N 的正整数矩阵。
现在要找出一个方案,让 WSN 总体用最短的时间把所有款式都绣出来
例1 [不可以每行都选时间最短的]:考虑如下3x3的矩阵:
1 2 2
2 1 2
2 2 9 ==> choose (2,2,2) = 6
例2:[有时候还必须 include 时间最长的]: 考虑如下3x3的矩阵:
1 4 4
4 1 4
4 4 5 ==> choose (1,1,5) = 7
当然,Naively, 可以把 N! 种可能性都试一遍。但是 N (max N = 75) 很大的时候,这个方法无法满足要求。是否有更聪明的算法呢?
原题链接:
http://code.google.com/codejam/contest/dashboard?c=32014#s=p3 |
i*********n 发帖数: 219 | |
c*********t 发帖数: 1861 | 3 哈,这张狠威风,偶笑纳了。。。
【在 i*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这张图片是送给你的 : 以表彰你的丰功伟绩
|
i*********n 发帖数: 219 | |
j*******a 发帖数: 2681 | 5 咱不出这样的题目成么,猫从来做不出的。。。
抗议~
我为什么,因为我还没有想出答案。好了,废话就不说了,大家帮我想这个题:
果我们把 WSN No.i 住房间 #j 的价格记做 A(i,j), 那么,A(i,j)组成了一个 N by N
的正整数矩阵。
的)
。。。
【在 c*********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 哈,这张狠威风,偶笑纳了。。。
|
n********6 发帖数: 1511 | 6 谢版兔隆恩。
【在 i*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 谢版主兔恩
|
s*******u 发帖数: 5796 | 7 motel没有这样做生意的啊!不同顾客入住房价不一样,还想不想干了?!告你
discrimination!疯兔你还是换个比喻好了。这样太confusing~ |
h********r 发帖数: 3291 | 8 我要是wsn,要么住霸王店,要么搭帐篷。住个店都怎么麻烦,你说以后还有哪个ppmm
会跟你出去玩?真是脑子彻底进水了。
(这个问题应该是np-complete,还是不要最便宜,只要差不多便宜就可以了。用随机
mutation+tunneling)
我为什么,因为我还没有想出答案。好了,废话就不说了,大家帮我想这个题:
果我们把 WSN No.i 住房间 #j 的价格记做 A(i,j), 那么,A(i,j)组成了一个 N by N
的正整数矩阵。
的)
。。。
【在 c*********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 哈,这张狠威风,偶笑纳了。。。
|
c*********t 发帖数: 1861 | 9 如你所愿,题目已做改动。
我土,什么叫做 tunneling 啊? Is it something like aborting search
pre-maturely?
ppmm
N
【在 h********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我要是wsn,要么住霸王店,要么搭帐篷。住个店都怎么麻烦,你说以后还有哪个ppmm : 会跟你出去玩?真是脑子彻底进水了。 : (这个问题应该是np-complete,还是不要最便宜,只要差不多便宜就可以了。用随机 : mutation+tunneling) : : 我为什么,因为我还没有想出答案。好了,废话就不说了,大家帮我想这个题: : 果我们把 WSN No.i 住房间 #j 的价格记做 A(i,j), 那么,A(i,j)组成了一个 N by N : 的正整数矩阵。 : 的) : 。。。
|
A*********t 发帖数: 7481 | 10 我觉得这个版都进水了。
。。不要问我为什么,因为我还没有想出答案。好了,废话就不说了,大家帮我想这个
题:
们把 WSN No.i 搞定 MM No.j 需要的时间记做 T(i,j), 那么,T(i,j)组成了一个 N
by N 的正整数矩阵。
不必要的流血事件,不可以让两个 WSN 去泡同一个MM。。。
【在 c*********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如你所愿,题目已做改动。 : 我土,什么叫做 tunneling 啊? Is it something like aborting search : pre-maturely? : : ppmm : N
|
D********e 发帖数: 475 | 11 I guess google wants an exact algorithm for this problem.
ppmm
N
【在 h********r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我要是wsn,要么住霸王店,要么搭帐篷。住个店都怎么麻烦,你说以后还有哪个ppmm : 会跟你出去玩?真是脑子彻底进水了。 : (这个问题应该是np-complete,还是不要最便宜,只要差不多便宜就可以了。用随机 : mutation+tunneling) : : 我为什么,因为我还没有想出答案。好了,废话就不说了,大家帮我想这个题: : 果我们把 WSN No.i 住房间 #j 的价格记做 A(i,j), 那么,A(i,j)组成了一个 N by N : 的正整数矩阵。 : 的) : 。。。
|
i*********n 发帖数: 219 | |
c*********t 发帖数: 1861 | 13 真是踏破旅游鞋。。。昨天无意中搜到一个 Hungarian 算法,O(N^4)把问题解决了。
思想方法是先找到(冲突的)局部最优,然后逐步放松(找次优)调整消除冲突。不过
这个算法比较 non-intuitive. 有兴趣的群众可以参考:
http://en.wikipedia.org/wiki/Hungarian_algorithm
真不知道那些得满分的疯子怎么会在2小时内记得这些东西。。。
,大家帮我想这个题:
的时间记做 T(i,j), 那么,T(i,j)组成了一个 N by N 的正整数矩阵。
【在 c*********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如你所愿,题目已做改动。 : 我土,什么叫做 tunneling 啊? Is it something like aborting search : pre-maturely? : : ppmm : N
|
D********e 发帖数: 475 | 14 Just realized this is maximum weighted bipartite matching. Should be easily
solvable with augmenting path algorithm.
【在 c*********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 真是踏破旅游鞋。。。昨天无意中搜到一个 Hungarian 算法,O(N^4)把问题解决了。 : 思想方法是先找到(冲突的)局部最优,然后逐步放松(找次优)调整消除冲突。不过 : 这个算法比较 non-intuitive. 有兴趣的群众可以参考: : http://en.wikipedia.org/wiki/Hungarian_algorithm : 真不知道那些得满分的疯子怎么会在2小时内记得这些东西。。。 : : ,大家帮我想这个题: : 的时间记做 T(i,j), 那么,T(i,j)组成了一个 N by N 的正整数矩阵。
|