哪能搞法——动态规划再试
不知道有没有读者试过了这个大包包，我试了一下，在我的 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)”
今天发现一本奇书
如果有这样一本书：
- 在科学发展历程中是完成划时代突破的巨著
- 行销六十年，出版五十年后重新发行
- Amazon 顾客评论 600 多条，平均四星评价
- 篇幅宏大，细节精美而又毫不重复，永远出乎读者意料
作为策划编辑的你，难道没有怦然心动吗？！
唐杜里考（伪）
唐杜里，又译天多利、唐肚里、唐多令等，源于印度西北部的旁遮普邦。印度名菜“唐杜里鸡”即其典型代表。制时先以酸奶浸之，覆以唐杜里香料，而后置于泥窑中烧熟。此菜之要领，在于其香料，以胡椒、丁香、柴桂、豆蔻、孜然、肉桂、草果、花椒、芫荽籽等磨粉配成，又可辅以大蒜、洋葱、辣椒等，烤制时香气四溢，引人食欲。相传玄奘西行取经时，曾遇险境，粮草俱绝，幸得当地善人以此菜相救，遂以“唐肚里”名之，取其入唐人腹中之意。后此菜传入中原，渐有演变。宋朝词人刘过登临武昌南楼时曾吃到此菜，口味稍甜，遂以菜名入词牌，赋得《糖多令·芦叶满汀洲》一词，成千古名篇。《红楼梦》中佳肴珍馐不可胜数，黛玉《唐多令》词更有“粉堕百花洲，香残燕子楼”语，言其香气之烈直可残燕羞花。此菜传入阿米利加后，凡三氏食肆无不有备，盛名欲与宫保鸡丁争锋。（误）
当浮一大白
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'.
“半个保险丝”之谜
在被我拖了好几个月的稿之后，在新年来临之际，《咨询的奥秘（续）：咨询师的百宝箱》的新译本终于上市了。作为译者，能够翻译温伯格先生的两本经典咨询作品，实在是一大幸事。有兴趣的读者，可以到图灵社区或豆瓣试读来阅读本书部分章节。
在翻译过程中，我多次就文字中遇到的问题向温伯格先生本人咨询，先生均一一作答。唯有一个问题未解，是关于第六章中的一个故事（本节亦可见于豆瓣试读）：
1969 年，暴风雪。雪堆已经攀上了窗台。景色固然壮美，可我们和六位客人整个圣诞节都要困在屋里了。不过既然宾·克劳斯贝能渡过难关，我们决定也要尽力而为。出门的车道被封住了，不过在房子下面的车库里有一捆木柴，冰柜里有一扇上好的牛肉，地下室里还有一柜子好酒。我们没觉得这是灾难，而是尽情享受节日聚会，可这时候水泵坏了。
实际上它也没全坏，更准确地说是坏了一半。不知道是什么原因，水泵转啊转啊，可抽上来的只有涓涓细流。我们还可以化雪水来喝，所以活命倒不是问题。哦，可能还是有问题的——没水冲马桶的话，在这个只有一个洗手间的房子里，八个人可是够受的。
幸运的是，我们的六位客人里有三个电气工程师：两个博士，另一个是机械工程和电气工程双硕士。一位博士艰难地下到地窖里去“瞧一眼”，我们剩下的几个人就安心地松了口气。
在一趟趟上楼下楼、一项项检查、一次次讨论、一套套理论之后，水泵一直转啊转啊转啊，水还是只有一点点。工程师们似乎江郎才尽了——看起来就是这样。
这时，一位不是工程师的客人发话了。这位金发女陶艺师提议说：“可能是保险丝的问题。”在不到一微秒的时间里，她的想法就遭到了你能想到的最尖酸刻薄的奚落。不过她却不为所动，坚持说：“为什么不可能是保险丝的问题？”
然后就有了三套完整的解释，理论层次虽有不同，不过最后都归结为一件事：根本不可能是保险丝嘛，因为泵还在转呢，虽然只是部分在转。
“那可能是半个保险丝嘛。”她说。工程师们开始居高临下地和她解释保险丝没有半个一说：“保险丝要么是好的，要么是坏的，没有中间态啊。”
“我家就有一半正常工作的保险丝。”陶艺师维护着自己的说法。话说到这一步，工程师们就转去讨论别的事情了。这样的说法根本不值得一驳。
几分钟之后，陶艺师不见了。我有点担心工程师敷衍的态度会让她不高兴，于是去找她，以尽主人之谊。后来我发现根本用不着操这个心。
她从地下室回来的时候正好碰上我。她不发一言，走到厨房水槽边拧开了水龙头。看着涌出的水，她带着胜利的笑容宣布：“我早就告诉他们是半个保险丝的问题。”
确实，还真是半个保险丝。更具体来说，把 120 伏转成水泵用的 240 伏所需的两根保险丝中的一根。一根保险丝烧断了以后，可怜的水泵就只能以额定电压的一半徒劳地在那儿抽水。泵是在转，可就是没什么作用。
故事就是这样了，可我还一下子没有反应过来。为什么烧断了一根保险丝之后就只剩下 120 伏了呢？难道不应该是整个断开了吗？看来学电的都掉进一样的圈里了……
Continue reading ““半个保险丝”之谜”
蚊
搬家记
定了要去加州，立刻就面临着搬家的问题。美国人挺流行的一种方式是自己弄一个 U-haul 之类的开过去，可我人在费城，这一路要不间断地开 40 多个小时，在我看来这需要至少五天。要是有人同行轮换陪聊也就罢了，一个人开实在有点吃不消，再加上沿途住宿吃饭以及安全考虑，还是不要冒这个险了。
找搬家公司来看我的房间，这位大叔拿着个 iPad 记我有桌子沙发以及多少箱子之类，第二天开出了一个将近七千刀的天价——按照一立方英尺平均七磅算，林林总总估计我有四千磅东西要搬。这玩意似乎比我当初从国内搬过来还要贵 :((
天知道我这几年怎么就在这两室公寓里面攒下了这么多的东西。在计算出差不多搬一磅东西需要一块五美金之后，我就开始在网上贴广告卖家具，卖掉那些减掉搬家费之后净价值为负的家具。依稀记得当初是怎么把沙发买回家的，怎么把餐桌买回家的，怎么把衣橱装起来的，怎么把书架拼起来的。这段时间，就像是看着时光倒流，看着它们一件件消失，留下生活中一点点的空白。挂在网上的价格，也从一个月之前的斤斤计算，到后来基本上是越来越不在意了，只是希望对方早点来。即便如此，我还是觉得这是我来美国之后最没有契约感的事情——很多人前一天还信誓旦旦一定要买，第二天就短信不回电话不接直接消失。最典型的是我卖俩简易书柜，一共才卖 15 块钱，却被放了三次鸽子。后来临走了我降到 10 块，立刻有两个人打电话过来，其中一位第二天冒雪来把它们搬走了。
在 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));