前面的方法已经非常快了，应该说很满意。那还有没有再优化的余地呢？
我们再来仔细看一下这个过程：深度优先搜索，逐级回溯，典型的二叉树遍历方式。为了方便说明，我标出了结点遍历的顺序：
Continue reading “0-1 背包问题详解 (4)”
分类： 技术相关
0-1 背包问题详解 (3)
哪能搞法——分支界限
我们先把动态规划的想法放一下，退一步来看看这个问题。每一个物品都可能放或者不放，如果用一个决策树来表示的话，就得到这样一棵满二叉树：
这对于 \(n\) 个物品就有 \(2^n\) 种放法，总共要计算 \(2^{n+1} – 2\) 个结点，当然是太多了。不过，有没有什么办法能让遍历的结点少一点呢？
0-1 背包问题详解 (2)
哪能搞法——动态规划再试
不知道有没有读者试过了这个大包包，我试了一下，在我的 2.30GHz i5 5300U 上，这个函数用 cPython 跑了…… 1632.07 秒，将近半个小时。照这个搞法，每次那个包有多大，就得搞出多少项。那个包的大小可是个任意数啊？这 $ W$ 比 $ 2^n$ 大都说不定呢？
Continue reading “0-1 背包问题详解 (2)”
0-1 背包问题详解 (1)
所有代码可见于：https://github.com/jameslao/Algorithmic-Pearls/tree/master/0-1-Knapsack
为什么要写这个系列
这些程序大部分都是 2013 年跟着 Tim Roughgarden 看算法课的时候写的，还算有些心得，尤其是优化的部分，似乎中文书中讲到的不是很多。而且也很久没有写博客了，回顾一下当初学过的东西也还有些收获。
背包问题是啥
不知道你还记不记得我们小时候看过的《太阳山》的故事：
从前，有弟兄俩，老大是个贪心的富人，老二是个穷人。
老二没有地，种老大的地。他一年到头在地里做活；可是老是吃不上，穿不上，租子交不够。
有一天，老二上山打柴。天都快黑了，他还坐在山上；他发愁，加上打柴，租子还是交不够。这时候，忽然刮起一阵黑风，飞来一只大鸟。大鸟落在他跟前，对他说：“你不用发愁。太阳山上有很多金子、银子，还有宝石。我背你上太阳山去吧！你从那儿可以拿些金子回来。”
老二爬到大鸟的背上。大鸟叫他闭上眼睛。他刚闭上眼睛，觉得飕一下子，就听见大鸟说：“到了。你看，有多少金子！去拿吧！你可不要贪心。这是太阳山。如果我们在这儿待得时间太长，赶上太阳回来，就把你烧死了。那时候，我也没办法救你。”
老二一边答应着，一边从大鸟的背上跳下来。哎呀！遍地是金子、银子、宝石，金光闪闪，晃得人睁不开眼睛。老二想了想，就拿一小块金子，装进口袋，要大鸟背他回去。大鸟问他为什么只拿一小块儿。他说够了。
老二又爬到大鸟的背上，闭上眼睛。飕一下子，大鸟落到他家门口了。他谢过大鸟，大鸟就飞走了。
老二有了金子，买了地，盖了房子。他早晨起来去种地，晚上回到新盖的房子里休息，日子过得很好。
老大见老二有金子，很眼红。他问老二的金子是哪儿来的。老二把大鸟背自己到太阳山的事告诉他了。
第二天，老大学着老二到山上去打柴。天快黑了，他故意不回家，坐在山上假装发愁。大鸟飞来了，也答应背他上太阳山去拿些金子。
大鸟背老大到了太阳山，嘱咐他不要贪心，像嘱咐老二一样，可是他连哼也不哼。他看见那么多金子、银子、宝石，忙着张开大布袋子，捡最大块儿的金子往里装。
老大拼命的往大布袋子里装金子，装个没完。大鸟催他回去，他说再让他拿几块。大鸟再催他回去，他还是这么说。最后，大鸟说：“时候到了！太阳马上就回来了！”他这才站起来，朝着大鸟走，摇摇晃晃的，大布袋子压得他走不稳了。没走几步，他又弯下腰来，说：“等一会儿。我再拿几颗宝石吧！”
正在这时候，火红的太阳回来了。它把烈火似的阳光喷到太阳山上。大鸟飞走了。老大被烧死了。
要是换你去拿，你会怎么拿呢？你是只拿一小块，还是拿到自己走不动？有没有什么办法，能够拿到最多的金子呢？
Continue reading “0-1 背包问题详解 (1)”
TeXLive 2013 / 2014 报错一例
最近在一台服务器上将 TeXLive 2013 更新到 2014，结果 XeLaTeX 不工作了。一直报
kpathsea: Running mktexfmt xelatex.fmt ... I can't find the format file `xelatex.fmt'!
查了一通，发现可以用这个命令来重建 fmt 文件
fmtutil --byfmt=xetex
然后就改报下面这个问题了
! I can't find file `dehypht-x-2013-05-26.tex'.
在 VMWare 下安装 Ubuntu 13.10 的共享文件夹问题
最近在 VMWare 下面装了一个 Ubuntu，但是共享文件夹总是用不了，每次一加载就报 “无法更新运行时文件夹共享状态: 在客户机操作系统内装载共享文件夹文件系统时出错。”
好在有高人解决了这个问题，虽然不是官方的：
1. 先选“重新安装 VMWare Tools”， 然后解压到 home。
2. 建这么一个 shell 脚本并 sudo 运行：
cd ~/vmware-tools-distrib/lib/modules/source sudo tar xf vmhgfs.tar sudo wget https://raw.github.com/rasa/vmware-tools-patches/master/patches/vmhgfs/vmhgfs-d_count-kernel-3.11-tools-9.6.0.patch sudo patch -p0 <vmhgfs-d_count-kernel-3.11-tools-9.6.0.patch sudo mv vmhgfs.tar vmhgfs.orig.tar sudo tar cf vmhgfs.tar vmhgfs-only cd ~/vmware-tools-distrib sudo ./vmware-install.pl
3. 一路回车之后重启。应该就好了。
查看补丁具体内容--- vmhgfs-only/inode.c 2013-08-15 22:32:22.000000000 -0700
+++ vmhgfs-only.patched/inode.c 2013-09-16 21:31:12.323041668 -0700
@@ -31,6 +31,9 @@
#include <linux/namei.h>
#endif
#include <linux/highmem.h>
+#if LINUX_VERSION_CODE >= KERNEL_VERSION(3, 11, 0)
+#include <linux/dcache.h>
+#endif
#include "compat_cred.h"
#include "compat_fs.h"
@@ -1890,7 +1893,11 @@
#endif
&inode->i_dentry,
d_alias) {
+#if LINUX_VERSION_CODE >= KERNEL_VERSION(3, 11, 0)
+ int dcount = d_count(dentry);
+#else
int dcount = dentry->d_count;
+#endif
if (dcount) {
LOG(4, ("Found %s %d \n", dentry->d_name.name, dcount));
return HgfsAccessInt(dentry, mask & (MAY_READ | MAY_WRITE | MAY_EXEC));
@@ -1943,10 +1950,12 @@
list_for_each(pos, &inode->i_dentry) {
int dcount;
struct dentry *dentry = list_entry(pos, struct dentry, d_alias);
-#if LINUX_VERSION_CODE < KERNEL_VERSION(2, 6, 38)
- dcount = atomic_read(&dentry->d_count);
-#else
+#if LINUX_VERSION_CODE >= KERNEL_VERSION(3, 11, 0)
+ dcount = d_count(dentry);
+#elif LINUX_VERSION_CODE >= KERNEL_VERSION(2, 6, 38)
dcount = dentry->d_count;
+#else
+ dcount = atomic_read(&dentry->d_count);
#endif
if (dcount) {
LOG(4, ("Found %s %d \n", (dentry)->d_name.name, dcount));
理解资产价格
两个月前，诺贝尔经济学奖颁给了法玛、汉森和席勒——无论这听起来是像是生物学奖同时发给了进化论和神创论，还是剑宗气宗联袂掌门，总归就是这个现状。这几位大神都搞了些什么理论呢？瑞典皇家科学院的经济学奖委员会为此写了一篇出色的综述，题为 Understanding Asset Prices，介绍整个资产定价的学科现状以及几位获奖者的工作。
“这篇文章几乎是一本自成体系的实证金融学研究生课程教材。”（芝加哥大学 John Cochrane 教授语 ）
现在我把它译成中文，并在正文中添加了指向参考文献的链接，方便读者查阅。译稿成稿仓促也未仔细润色，有不妥之处还请读者指正。
使用声明：本文不是瑞典皇家科学院给出的官方译文。本文由译者自行译为中文，并经瑞典皇家科学院许可予以公开，允许免费分发。译者保理解资产价格留所有权利。
猜硬币的游戏
快两个月没更新了，成天瞎忙…… 我们来看一个简单的题目吧，选自俄罗斯大神阿诺德（Влади́мир И́горевич Арно́льд）出的一百道题。[1] 题目是这样的：
一位游戏者藏起一枚 10 戈比或 20 戈比的硬币，另一位游戏者猜。猜对了就可以把硬币赢走，猜错了就要付出 15 戈比。这是个公平的游戏吗？双方最佳的混合策略是怎样的？
任意两个自然数互质的概率？
试问：任取两个自然数，它们互质的概率是多少？即以等概率取两个自然数 \( x, y \in \{1,2,\ldots,n\}\)，令 \( P_2(n)\) 是 \(x\)、\(y\) 互质的概率，求 \(\lim_{n\to \infty} P_2(n)\) 。
随机多个色子的期望和方差
这道题的原题来自于 Project Euler 389。
扔一个均匀的四面体色子，记下点数 T；
扔 T 个均匀的六面体色子，把所有的点数加起来，记为 C；
扔 C 个均匀的八面体色子，把所有的点数加起来，记为 O；
扔 O 个均匀的十二面体色子，把所有的点数加起来，记为 D；
扔 D 个均匀的二十面体色子，把所有的点数加起来，记为 I；
求 I 的方差。