发帖数: 1 | 1 千万别惹计算机教授。
最近，圣母大学计算机系终身副教授，博士生导师，并兼任电子系终身副教授史弋宇经
历了一件惊心动魄的事：
12月中下旬的周末，史教授原本计划开车带一家人由芝加哥O’Hare经纽约前往百慕大
的度假旅行，在途中一座加油站停车检查车胎时，遇到了两名持枪劫匪。劫匪抢走了史
教授的钱包和Mazda CX-9汽车，让这次旅行泡汤。
转折的地方在于，史教授利用马自达的手机发动应用程序（Mazda Mobile Start，MMS
），成功定位到车辆的相对位置，并用计算机算法中最直接的greedy approach（贪心
算法），将车辆位置搜寻了出来。最终，在被抢不到24小时，史教授成功把车追回。
连现场的警察都感叹：
“They shouldn’t have messed up with computer science professors!”
被抢：两个劫匪持枪，抢走所有行李！
按原计划，史教授一家人开车从印第安纳的South Bend出发，大约中部时间12:00 到达
芝加哥中国城，当时发现Mazda CX-9提示胎压异常，因此史教授决定午饭后开车前往中
国城附近的一家Sh... 阅读全帖 |
|
p*****2
发帖数: 21240 | 2 前两天有人问DP和Greedy的区别，今天做了一道题不错。我先用DP解，当时感觉有点别
扭，因为觉得好像有条件没有用上，结果超时。后来才意识到这题是Greedy. 想感觉一
下DP和Greedy的可以练练。
Sergey attends lessons of the N-ish language. Each lesson he receives a
hometask. This time the task is to translate some sentence to the N-ish
language. Sentences of the N-ish language can be represented as strings
consisting of lowercase Latin letters without spaces or punctuation marks.
Sergey totally forgot about the task until half an hour before the next
lesson and hastily scribbled some... 阅读全帖 |
|
b***u
发帖数: 12010 | 3 greedy难在不知道greedy可以。用dp绕半天浪费时间。greedy关键要能证明能贪
in |
|
p*****2
发帖数: 21240 | 4
是。因为做过很多类似的DP题，上来就往DP那里想了。做的时候才发觉DP帮助不明显。
但是测试用例也都过了，就提交了。这题证明greedy可以也得花一些时间。不是很直观
。如果只是有思路的话，还是会在greedy和dp只见纠缠。感觉比赛的时候很难掌握呀。
另外，上一下greedy的代码。
public class test2 {
static String s;
static int k;
static HashSet pairs = new HashSet();
static boolean isForbidden(char[] arr) {
Arrays.sort(arr);
return pairs.contains(new String(arr));
}
static int Play(String str) {
int count = 0;
int count1 = 0;
int count2 = 0;
int j = 0;
for (int... 阅读全帖 |
|
s*****r
发帖数: 108 | 5 是的...刚开始学感觉 greedy 简单，dp 难搞
因为一开始做的 greedy 确实是简单题，dp 入门难一点
后来做多 dp 发现 dp 又容易写 准确率又高
而 greedy 就难搞了 牵扯到数学证明
其实另一方面是水 dp 太多了 就考一个方程 其实牵扯到优化的 dp 也挺难搞的
比如有个题说 10^9 这么长的桥上有只青蛙每次跳 S~T 步 1<=S<=T<=10，桥上 M <=
100 个石子，问从头跳过桥最少踩几个。方程是挺好写的 只是优化也没那么显然
再比如说状态压缩的 dp，四边形不等式优化一类方程，插头 dp，斜率优化...
还有的一看是 dp 其实用贪心更快 其实 dp 也是很难搞的 只是面试难度不高而已也不
必深入 |
|
t*******l
发帖数: 3662 | 6 大牛总是说亏就是买高了 然后卖早了
考虑到现在的大盘情况 我看应该这样用
greedy，就是入点一定要等global optimum，
出点找local optimum
两边都找最佳值不可能 而且风险太大 还不如
进的时候用maximum greedy状态。出的时候用
minimum greedy的状态 |
|
N****p
发帖数: 1691 | 7 你怎么知道现在是greedy还是scared
你自己作为市场的一分子还在greedy 怎么就知道别人都在scared |
|
a*******m
发帖数: 14194 | 8 今天早上的BBC早新闻，有人听没？ Nov 14, 2012
BBC做了个钓鱼岛问题的采访小专题，
一个倭杂小娘们在采访中说，
China has very big territory. Japan has very small territory,
only some islands. Now China try to grab japan's Senkaku-guntō（钓鱼岛），
and take all the gas and oil resource. China is too greedy, too greedy!
哈哈，这个倭杂小娘们就差说，it is unfair 了。
前段时间看到的 钓鱼岛专题
https://www.youtube.com/playlist?list=PLfxN0HXJEM4GLh4sCLqL6ZGTFboMQ2zhd&
feature=view_all
|
|
w*********g
发帖数: 30882 | 9 日本只有1亿多人口，中国有13亿人口要养活，对资源的需求显然不是一个数量级的。
日本的人口仅仅相当于中国的十分之一，却要求跟中国平分资源，日本too greedy,
too greedy. |
|
T****t
发帖数: 11162 | 10 就是使用学生用了greedy算法
: 他第二天带学生找车时下了高速以后那段时间用的greedy算法
|
|
发帖数: 1 | 11 如果对方车是运动的，就要在对方车的参考系里用这个所谓的greedy算法，在那个参考
系里要转直角弯，但在地面参考系里就不一定是直角弯，具体转多少度，要根据两车的
速度矢量计算出来。
这方法即跟greedy没关系，而且本身就是错的。
让他找到车的原因，不是什么算法，而是不要老命的死追再加运气。事后再慢慢吹牛逼
当时用了什么算法。
史教授可以吹CS的人是不好惹的，但他忘了还有一种人是物理转行CS. |
|
p*****2
发帖数: 21240 | 12 感觉比DP难一个档次
DP还是比较容易的，毕竟属于brute force，miss不了啥东西。greedy就不一样了，很
难证明正确性，自己做了也不清楚到底对不对。想证明一下，发现特别费脑子。DP想起
来要清晰很多。看来做greedy的题还需要加强呀。 |
|
r**********o
发帖数: 50 | 13 大牛， regular expression matching是不是也可以用greedy的？ wildcard matching
的比较好写，regular expression 这题的greedy不会诶 |
|
a***m
发帖数: 5037 | 14 先定量描述什么是 greedy 和 scared 吧
不然没有可操作性 |
|
n*****n
发帖数: 100 | 15 【 以下文字转载自 Quant 讨论区 】
发信人: nowoman (纵横江湖), 信区: Quant
标 题: 问一个在network 中Greedy algorithm的问题
发信站: BBS 未名空间站 (Mon Jan 28 16:00:23 2008)
比如任意一个network, 每条link上有两个cost=(a,b).现在我们要找一条路径 which,
minimize the sum of \sum (a_i) under the constaint of \sum (b_i) <= B. 在这
种情况下,如果我们想用greedy algorithm,该如何用呢?谢谢! |
|
k**y
发帖数: 320 | 16 not quite sure i understand. maybe the following example helps:
{[0,10], [11,20], [10,11]} greedy picks [10,11] but the opt
solution is [0,11]+[11,20].
it is not hard to prove greedy gives > 0.5 approximation. |
|
I*****y
发帖数: 6402 | 17 还是说说zlcs
8毛钱的时候进入一回，到1.12的时候出了，看着还是涨，然后在1.19的时候又入，到
了1.5的时候出手；跌到1.4的时候入了更多，上周二到了1.6多，心里有点greedy了，
没卖，没曾想啊，到周五的时候居然红了。今天周一开盘还不错，不过在8点多的时候
，居然跳水到了1.24，还好，我在1.35的时候基本清仓了。
最后一句话感悟：见好就收一段时间，享受胜利果实，不能太greedy。没亏，就是白忙
活了…… |
|
d***y
发帖数: 634 | 18 这事和greedy算法有屁关系？有了马自达那个软件提供方向和距离，不是白痴都知道距
离越短离车越近。不过在芝加哥敢去找车确实有勇气。 |
|
发帖数: 1 | 19 关键词：
回国、电脑、芯片、融资、华为
非关键词：
马自达
[在 danfy (danfy) 的大作中提到：]
:这事和greedy算法有屁关系？有了马自达那个软件提供方向和距离，不是白痴都知道
距离越短离车越近。不过在芝加哥敢去找车确实有勇气。 |
|
|
l*w
发帖数: 3758 | 21 文科生写的软文。跟你妈算法有屁关系
：千万别惹计算机教授。
：最近，圣母大学计算机系终身副教授，博士生导师，并兼任电子系终身副教授史弋宇
经历了一件惊心动魄的事：
：12月中下旬的周末，史教授原本计划开车带一家人由芝加哥O’Hare经纽约前往百慕大
：的度假旅行，在途中一座加油站停车检查车胎时，遇到了两名持枪劫匪。劫匪抢走了
史教授的钱包和Mazda CX-9汽车，让这次旅行泡汤。
：转折的地方在于，史教授利用马自达的手机发动应用程序（Mazda Mobile Start，
MMS
：），成功定位到车辆的相对位置，并用计算机算法中最直接的greedy approach（贪心
：算法），将车辆位置搜寻了出来。最终，在被抢不到24小时，史教授成功把车追回。
：连现场的警察都感叹：
： “They shouldn’t have messed up with computer science professors!”
：被抢：两个劫匪持枪，抢走所有行李！
：.......... |
|
B*Q
发帖数: 25729 | 22 用动态规划是不是能厉害点
[在 SLE (嗯，就这样定了。) 的大作中提到：]
:greedy算法是最没有技术含量的算法。 |
|
发帖数: 1 | 23 如果距离一直没变，你又能确定走过了一个环，那不是就可以确定车在圆心。 GREEDY
听起来有点牵强，不过的确就是那么个意思。 |
|
a**e
发帖数: 8800 | 24 这个水平还好意思扯淡？
随便找两个方向开，找到俩最短位置，在地图上画俩相切的圆，切点就是位置。
还击把greedy算法
MMS |
|
B*Q
发帖数: 25729 | 25 俺觉得索南们对标题里的greedy的理解是错的 |
|
l****o
发帖数: 5435 | 26 最近一个圣母大学教授史弋宇还用greedy 算出了被劫匪抢走的汽车位置。超燃！！ |
|
发帖数: 1 | 27 gps定点，然后greedy算过去最近路程。然后派学生souch chicago去取车。 |
|
发帖数: 1 | 28 县沿着一个方向找到信号最强，然后再沿着另外一个方向，这就是greedy算符 |
|
发帖数: 1 | 29 他第二天带学生找车时下了高速以后那段时间用的greedy算法 |
|
发帖数: 1 | 30 没买车全保, 不顾学生的安全, 还想把损失捞回来, 就叫greedy |
|
l*****r
发帖数: 687 | 31 给你们小将丢脸了
小心党妈护着他，下次回国抓你嫖娼
: 没买车全保, 不顾学生的安全, 还想把损失捞回来, 就叫greedy
|
|
发帖数: 1 | 32 那个方法前提是对方车是静止的。如果对方车是运动的，就要在对方车的参考系里用这
个所谓的greedy算法，在那个参考系里要转直角弯，但在地面参考系里就不一定是直角
弯，具体转多少度，要根据两车的速度矢量计算出来 |
|
发帖数: 1 | 33 good point! 另外，车是静止的用不用这个greedy算法真没有太大关系，no country
for old man里的杀手围着motel转了几圈，也很快确定了目标在哪个房间 |
|
|
T*********r
发帖数: 11175 | 35 【 以下文字转载自 WaterWorld 讨论区 】
发信人: TechniColor (坚决服从rourou的领导), 信区: WaterWorld
标 题: 碰到个非常greedy的韩国大妈realtor
发信站: BBS 未名空间站 (Sat Jul 17 17:12:05 2010, 美东)
借lg ID发文。
新工作relocation（fresh phd），这周在新地方看房子（租房）。这realtor是今后公
司一大姐介绍的。房子是我自己网上看好的（后来发现一朋友也住那儿，就算她refer
我了），和apartment manager时间都是我约的。本来昨天打算看4，5处房子，看了这
第一处（就是我朋友住的地方）就决定签这里了，别的也没看。今天去填application
（realtor没去），我写我朋友refer。下午这韩国大妈就打电话，一定insist要我改成
她refer我的。我说relo公司不是已经pay她了吗，她说那钱不够。
其实给我朋友还是给她本来也没什么，只是从一开始电话联系我就发现跟这韩国人很难
沟通好，然后昨天带我看房子，她事先还邀功说自己前一天都来侦察 |
|
w****a
发帖数: 710 | 36 可以用DP但是greedy更简单，jump game就是个好例子啊。哈哈 |
|
|
J****8
发帖数: 117 | 38 1D 问题如下：有n个点x1, x2,…, xn , 要求用最少数量的单位长线段覆盖这些点。
解法应该可以用 greedy 算法：就是从左至右的顺序覆盖给定的n个点
现在扩展到2D, 平面上n个点x1, x2,…, xn，要求用最少数量的单位正方形覆盖这些点
，该怎么做呢？好像不能简单的从1D推过来。
求大牛解答 |
|
发帖数: 1 | 39 这个一行一行排,如果有不符合的就No，这算greedy吧 |
|
|
T*********r
发帖数: 11175 | 41 【 以下文字转载自 WaterWorld 讨论区 】
发信人: TechniColor (坚决服从rourou的领导), 信区: WaterWorld
标 题: 碰到个非常greedy的韩国大妈realtor
发信站: BBS 未名空间站 (Sat Jul 17 17:12:05 2010, 美东)
借lg ID发文。
新工作relocation（fresh phd），这周在新地方看房子（租房）。这realtor是今后公
司一大姐介绍的。房子是我自己网上看好的（后来发现一朋友也住那儿，就算她refer
我了），和apartment manager时间都是我约的。本来昨天打算看4，5处房子，看了这
第一处（就是我朋友住的地方）就决定签这里了，别的也没看。今天去填application
（realtor没去），我写我朋友refer。下午这韩国大妈就打电话，一定insist要我改成
她refer我的。我说relo公司不是已经pay她了吗，她说那钱不够。
其实给我朋友还是给她本来也没什么，只是从一开始电话联系我就发现跟这韩国人很难
沟通好，然后昨天带我看房子，她事先还邀功说自己前一天都来侦察 |
|
|
r******n
发帖数: 626 | 43 关键是现在没多少人fearful啊，倒是不少人很greedy |
|
p*********r
发帖数: 7944 | 44 Be greedy when others are fearful，应该是在说大盘吧？ |
|
p*********r
发帖数: 7944 | 45 不要怕，同他们斗到底。
卖家太greedy了，把这个case弄成sensational。 |
|
x*******1
发帖数: 28835 | 46 longhorn triggered the first gun!!!They are the most greedy and will be
remembered in college football history. |
|
g****p
发帖数: 94 | 47 有"greedy stays ahead"，和"exchange"两种，看不太明白
哪位大侠能给讲解一下？
多谢！ |
|
n*****n
发帖数: 100 | 48 比如任意一个network, 每条link上有两个cost=(a,b).现在我们要找一条路径 which,
minimize the sum of \sum (a_i) under the constaint of \sum (b_i) <= B. 在这
种情况下,如果我们想用greedy algorithm,该如何用呢?谢谢! |
|
B*****n
发帖数: 498 | 49 可是greedy algorithm无法garantee optimality啊。
, |
|
c*****t
发帖数: 1879 | 50 【 以下文字转载自 Programming 讨论区 】
【 原文由 coconut 所发表 】
Activity selection problem. For those people who don't remember,
it asks one to pick max # of non-overlapping segments. The optimal
strategy is to sort the segments according to where it ends and
pick accordingly. However, this is not what I am asking.
I am asking for a counter example that that Minimum Overlap greedy
(sort segments according to minimum overlap). I knew that it is
not optimal (I did it before), but apparently I forgot the solut |
|
