‘技术相关’ 分类的存档

0-1 背包问题详解 (4)

2015年9月7日 没有评论

前面的方法已经非常快了,应该说很满意。那还有没有再优化的余地呢?

我们再来仔细看一下这个过程:深度优先搜索,逐级回溯,典型的二叉树遍历方式。为了方便说明,我标出了结点遍历的顺序:
knapsack_tiny_arrow
阅读全文…

0-1 背包问题详解 (3)

2015年8月24日 没有评论

哪能搞法——分支界限

我们先把动态规划的想法放一下,退一步来看看这个问题。每一个物品都可能放或者不放,如果用一个决策树来表示的话,就得到这样一棵满二叉树:

fulltree

这对于 \(n\) 个物品就有 \(2^n\) 种放法,总共要计算 \(2^{n+1} – 2\) 个结点,当然是太多了。不过,有没有什么办法能让遍历的结点少一点呢?

阅读全文…

0-1 背包问题详解 (2)

2015年8月18日 没有评论

哪能搞法——动态规划再试

不知道有没有读者试过了这个大包包,我试了一下,在我的 2.30GHz i5 5300U 上,这个函数用 cPython 跑了…… 1632.07 秒,将近半个小时。照这个搞法,每次那个包有多大,就得搞出多少项。那个包的大小可是个任意数啊?这 $ W$ 比 $ 2^n$ 大都说不定呢?
阅读全文…

0-1 背包问题详解 (1)

2015年8月17日 没有评论

所有代码可见于:https://github.com/jameslao/Algorithmic-Pearls/tree/master/0-1-Knapsack

为什么要写这个系列

这些程序大部分都是 2013 年跟着 Tim Roughgarden 看算法课的时候写的,还算有些心得,尤其是优化的部分,似乎中文书中讲到的不是很多。而且也很久没有写博客了,回顾一下当初学过的东西也还有些收获。

背包问题是啥

不知道你还记不记得我们小时候看过的《太阳山》的故事:

cover

从前,有弟兄俩,老大是个贪心的富人,老二是个穷人。

老二没有地,种老大的地。他一年到头在地里做活;可是老是吃不上,穿不上,租子交不够。

有一天,老二上山打柴。天都快黑了,他还坐在山上;他发愁,加上打柴,租子还是交不够。这时候,忽然刮起一阵黑风,飞来一只大鸟。大鸟落在他跟前,对他说:“你不用发愁。太阳山上有很多金子、银子,还有宝石。我背你上太阳山去吧!你从那儿可以拿些金子回来。”

老二爬到大鸟的背上。大鸟叫他闭上眼睛。他刚闭上眼睛,觉得飕一下子,就听见大鸟说:“到了。你看,有多少金子!去拿吧!你可不要贪心。这是太阳山。如果我们在这儿待得时间太长,赶上太阳回来,就把你烧死了。那时候,我也没办法救你。”

老二一边答应着,一边从大鸟的背上跳下来。哎呀!遍地是金子、银子、宝石,金光闪闪,晃得人睁不开眼睛。老二想了想,就拿一小块金子,装进口袋,要大鸟背他回去。大鸟问他为什么只拿一小块儿。他说够了。

老二又爬到大鸟的背上,闭上眼睛。飕一下子,大鸟落到他家门口了。他谢过大鸟,大鸟就飞走了。

老二有了金子,买了地,盖了房子。他早晨起来去种地,晚上回到新盖的房子里休息,日子过得很好。

老大见老二有金子,很眼红。他问老二的金子是哪儿来的。老二把大鸟背自己到太阳山的事告诉他了。

第二天,老大学着老二到山上去打柴。天快黑了,他故意不回家,坐在山上假装发愁。大鸟飞来了,也答应背他上太阳山去拿些金子。

大鸟背老大到了太阳山,嘱咐他不要贪心,像嘱咐老二一样,可是他连哼也不哼。他看见那么多金子、银子、宝石,忙着张开大布袋子,捡最大块儿的金子往里装。

老大拼命的往大布袋子里装金子,装个没完。大鸟催他回去,他说再让他拿几块。大鸟再催他回去,他还是这么说。最后,大鸟说:“时候到了!太阳马上就回来了!”他这才站起来,朝着大鸟走,摇摇晃晃的,大布袋子压得他走不稳了。没走几步,他又弯下腰来,说:“等一会儿。我再拿几颗宝石吧!”

正在这时候,火红的太阳回来了。它把烈火似的阳光喷到太阳山上。大鸟飞走了。老大被烧死了。

要是换你去拿,你会怎么拿呢?你是只拿一小块,还是拿到自己走不动?有没有什么办法,能够拿到最多的金子呢?
阅读全文…

TeXLive 2013 / 2014 报错一例

2015年3月3日 没有评论

最近在一台服务器上将 TeXLive 2013 更新到 2014,结果 XeLaTeX 不工作了。一直报

查了一通,发现可以用这个命令来重建 fmt 文件

然后就改报下面这个问题了

阅读全文…

在 VMWare 下安装 Ubuntu 13.10 的共享文件夹问题

2014年3月3日 没有评论

最近在 VMWare 下面装了一个 Ubuntu,但是共享文件夹总是用不了,每次一加载就报 “无法更新运行时文件夹共享状态: 在客户机操作系统内装载共享文件夹文件系统时出错。”
好在有高人解决了这个问题,虽然不是官方的:

1. 先选“重新安装 VMWare Tools”, 然后解压到 home。
2. 建这么一个 shell 脚本并 sudo 运行:

3. 一路回车之后重启。应该就好了。

参考来源在这里这里。感谢补丁的作者。

查看补丁具体内容

理解资产价格

2013年12月20日 没有评论

两个月前,诺贝尔经济学奖颁给了法玛、汉森和席勒——无论这听起来是像是生物学奖同时发给了进化论和神创论,还是剑宗气宗联袂掌门,总归就是这个现状。这几位大神都搞了些什么理论呢?瑞典皇家科学院的经济学奖委员会为此写了一篇出色的综述,题为 Understanding Asset Prices,介绍整个资产定价的学科现状以及几位获奖者的工作。

“这篇文章几乎是一本自成体系的实证金融学研究生课程教材。”(芝加哥大学 John Cochrane 教授语

现在我把它译成中文,并在正文中添加了指向参考文献的链接,方便读者查阅。译稿成稿仓促也未仔细润色,有不妥之处还请读者指正。

使用声明:本文是瑞典皇家科学院给出的官方译文。本文由译者自行译为中文,并经瑞典皇家科学院许可予以公开,允许免费分发。译者保留所有权利。

理解资产价格
标题: 理解资产价格 (5420 clicks)
Size: 660 KB

猜硬币的游戏

2013年10月3日 2 条评论

Guess

快两个月没更新了,成天瞎忙…… 我们来看一个简单的题目吧,选自俄罗斯大神阿诺德(В. И́. Арно́льд)出的一百道题。[1] 题目是这样的:

一位游戏者藏起一枚 10 戈比或 20 戈比的硬币,另一位游戏者猜。猜对了就可以把硬币赢走,猜错了就要付出 15 戈比。这是个公平的游戏吗?双方最佳的混合策略是怎样的?

阅读全文…

分类: 技术相关 标签: ,

任意两个自然数互质的概率?

2013年7月25日 没有评论

试问:任取两个自然数,它们互质的概率是多少?即以等概率取两个自然数 \( x, y \in \{1,2,\ldots,n\}\),令 \( P_2(n)\) 是 \(x\)、\(y\) 互质的概率,求 \(\lim_{n\to \infty} P_2(n)\) 。

阅读全文…

《企业软件交付:敏捷与高效管理精要》中译本

2013年7月16日 没有评论

企业软件交付  OrigCover

这本书基本是去年年底翻译的,算是和本职工作比较相关的一本书。作者 Alan W. Brown 教授是英国萨里大学萨里商学院创业与创新教授,并曾任原 IBM Rational 欧洲的首席技术官,在全欧洲领导过众多企业解决方案、流程改进和敏捷实践相关的软件战略项目。原书中谈到的不少方法都值得在工作中思考借鉴,翻译本身也是一个很好的学习过程。特别值得一提的是书中给出的案例,有经验也有教训,十分难能可贵。感兴趣的同学可以看看样章,也可在 China-Pub 或者京东上订购。

阅读全文…