/* 课本0-1背包。 程序功能：将物体只能一次放入包中，要不超过总量 且 价值最大 经过vc8.0编译通过 * */ #include <iostream> using namespace std; #define N 10 #define C 50 void knapsack(int * v,int *w,int wlength,int c,int(*m)[C+1]) { int n=wlength-1; int jmax=std::min(w[n]-1,c); for(int j=0;j<=jmax;j++) m[n][j]=0; for(int j=w[n];j<=c;j++) m[n][j]=v[n]; for(int i=n-1;i>1;i–) { jmax=std::min(w[i]-1,c); for(int j=0;j<=jmax;j++) m[i][j]=m[i+1][j]; for(int j=w[i];j<=c;j++) m[i][j]=std::max(m[i+1][j],m[i+1][j-w[i]]+v[i]); } m[1][c]=m[2][c]; if(c>=w[1]) m[1][c]=std::max(m[1][c],m[2][c-w[1]]+v[1]); } […]
Daily Archives: 2013/04/03
/* 课本 0-1背包 加上体积限制。 程序功能：将物体只能一次放入包中，要不超过总量、总体积且 价值最大 经过vc8.0编译通过 * */ #include <iostream> #include <iomanip> using namespace std; #define N 10 //物品的可选数量 #define C 40 //包的最大可容纳重量 #define E 28 //包的最大可容纳体积 //动态规划算法 void knapsack(int * v,int *w,int wlength,int c,int *e,int ee,int (*m)[C+1][E+1]) { int n=wlength-1; //—————————————– //递归计算的第一步 //求出当物品只有n的解 int jmax = std::min(w[n]-1,c); int jmax2 = std::min(e[n]-1,ee); for(int j=0;j<=jmax;j++) for(int k=0;k<=jmax2;k++) m[n][j][k] = 0; […]
0-1背包2
/* 课本3-1-1。 程序功能：求解最长公共递增子序列 经过vc8.0编译通过 * */ #include <iostream> #include <string.h> using namespace std; #define N 11 //——————————————————— //最长公共子序列求解 int lcslength(int * x,int m,int * y,int n,int (*b)[N]) { int c[N][N]; int i; for(i=0;i<=n;i++) {c[0][i]=0;c[i][0]=0;} for(i=1;i<=m;i++) { for(int j=1;j<=n;j++) { if(x[i]==y[j]) { c[i][j]=c[i-1][j-1]+1; b[i][j]=1; } else if(c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=2; } […]
求解最长公共递增子序列
最长单调递增子序列问题的定义： 设计一个O(n2)时间的算法，找出由n个数组组成的序列的最长单调递增子序列。 子问题的定义： 对于求解N规模的数组，n-1,n-2,…,1 长度的数组构成了问题的子问题，子问题的详细定义是：求解以第n-1,n-2,…,1 个元素为最大值的最长子序列。 最优子结构： 第n个元素的最长子序列的长度是基于前n-1个元素最长子序列的基础之上，也就是第n个元素的最长子序列长度，是前n个元素的中最长的子序列长度+1。 解决的办法： 从第1个元素开始进行循环，不断地求出1,2,3,..,n元素为最大值的最长子序列长度，然后通过回溯查找最长子序列。 具体算法： Input 第一行：n，代表要输入的数列的个数 第二行：n个数，数字之间用空格格开 Output 最长单调递增子序列，数字之间用空格格开 Sample Input 5 1 3 5 2 9 Sample Output 1 3 5 9 C程序： #include <stdio.h> #include <stdlib.h> void findAllMax(int *,int *,int *,int); void trackBack(int *,int *,int *,int); […]
动态规划法 寻找最长单调递增子序列
After finished <Basic Engish> course & <engineering mathimatics> course, we started <Design and analysis of algorithms>. Frankly, I don’t familiar with most of them, although I’m a programmer with over ten years of experiences. I believe the reason of this is I’m not an algorithm researcher, but IMHO most of […]
我学：Design and analysis of algorithms
这是视频的演讲者是 Simon Sinek。这也是一个非常不错的演讲，当然这并不一定代表认同他对一些公司的看法和讲法，但重要的那种思想。我们做事件和表达必须从内而外。而不是自外而内。作为一点衔接，让我感触较深的是，就是前面提到我听：Richard St. John: 8 secrets of success这篇文章一样，作为一名员工，必须用心去做事，才可能成为一名好员工。举个例子： 公司从来不主动要求员工加班，但必如果一个员工真的认为自己的成长是跟公司、跟工作紧密连接在一起的，那不用要求，他自己就要用心，甚至拼了老命去工作。就像他提到的那样：The goal is not just to hire people who need a job; it’s to hire people who believe what you believe. I always say that, you know, if you hire people just because they can do a job, they’ll work for […]
我听：How great leaders inspire action
精华课程分享：成功的8个秘诀。 这是一篇很短的TED视频，只有3分多钟，但完全可以说“浓缩的都是精华”。 其中最让我深有感触的，也是我选择把这篇演讲放上来的原因是这一句话：Carol Coletta says, “I would pay someone to do what I do.” 我所在的公司其实一直都没怎么赚到钱，但是我们的老板却一直一直一直在往里边投钱，而且在许多时候的许多决策都让我们许多人都看不懂（废话，你要是看懂了，你不也成了Chairman of the Board了？）。 举个例子来说：我们今年不卖XXXX产品，RD努力做好XXXX产品。 OK，我明白，单纯这样讲可能你看不懂，那我换个说法：RD不要理会Sales的那些XXXX产品有YYYY bug、缺ZZZZ功能的抱怨（事实上连RD都知道有些问题很急，甚至有可能RD稍微努力的去配合一下，KKKK项目就能成功了），我想要做的是另外一个 功能/产品，而这个新功能/新产品可能几年内都带不来一分钱的收入，但谈下这个KKKK项目有可能会带来可观的收入，对业务的拓展及数年来的亏损有所帮 助…… 这样讲，也许你能有一点点的明白了吧？ 所以，当我在课堂上听到这句话的时候 Carol Coletta says, “I would pay someone to do what I do.”，真的被深深的感触到了，我们的董事长经营这家公司就是为了一种热爱，他爱这个产品，所以他愿意为这个产品投入大笔大笔的钱（哪怕连续的亏损），同时，他也愿意付钱给同样热爱这个产品的人让他们跟他一起工作。 以下为我专门到网上搜到的这个视频相关的英文原文： Richard St. John: 8 secrets of success http://www.ted.com/talks/richard_st_john_s_8_secrets_of_success.html About this talk Why […]
我听：Richard St. John: 8 secrets of success
1 最近一直在TED官方网站上看视频，尤其是看到杨澜的演讲，不知道为什么我非常激动。通过她17分钟的演讲让我更近一步的了解了杨澜这个人，还有中国现在的一些比较有意思的文化现象。 杨澜在TED上的演讲。我觉得是一次很不错的presentation.吐字清晰最重要，杨澜做到了。说她稀烂的…请你们别眼高手低。自己在家录一段看能不能有这个一半强= = 我欣赏杨澜 做为在TED演讲的极少数的中国人 沙沙的声音、气场和british accent玩的恰到好处 讲的关于中国的也都非常中肯 已经很不错了~~ from: http://www.ted.com/talks/yang_lan.html 杨澜介绍： 国内著名资深电视节目主持人。曾在国内具有强大影响力的电视台担任电视栏目主持，以极具亲和力的主持风格倍受广大电视观众的喜爱。曾主持《正大综艺》、《杨澜访谈录》等电视栏目；曾被评选为“亚洲二十位社会与文化领袖”、“能推动中国前进、重塑中国形象的十二位代表人物”、“《中国妇女》时代人物。 更多介绍：http://baike.baidu.com/view/26288.htm 视频收看地址：http://www.unsv.com/material/news/2011/10/10/Yang_Lan_TED_Speech/ The night before I was heading for Scotland, I was invited to host the final of “China’s Got Talent” show in Shanghai with the 80,000 live audience in the stadium. Guess who was the performing […]
我听：The generation that’s remaking China
Andrew Mason被解雇了，该说点啥呢？不知道！好吧，那听听人家是怎么说的？还有Andrew Mason自己是怎么说的？ I don’t root for failure and don’t believe that dancing on graves is ever the way to go. It’s an especially appropriate personal creed when a good guy who I think overplayed his hand decides to retreat throwing rose petals instead of grenades. Andrew Mason is out […]
Andrew Mason’s Daily Deal: ‘I Got Fired Today’
我在LinkedIn上看到这篇文章，感觉写得非常不错，所以就转过来。如果有时间的话，可以考虑给翻译一下。这样可以跟一些懒人一起分享学习。 Here are ten traits that any great employer should recognize and reward instantly. Zero Creatives/Getty As a longtime employer of dozens, I was always grateful to have good employees. It takes a lot to recruit and maintain top talent. Every once in a while special employees come along that […]
10 Things Really Amazing Employees Do
把我的C盘空间用EASEUS Partition Master 8.0.1调大了一点，以使C盘不再一直处于空间不够的警告，结果重启Windows之后就出现错误 error: incompatible license.Entering rescue mode… grub rescue> 首先交待一下我的环境：我的系统比较复杂，由于工作需要，共装了三个OS：一个Windows 7，一个Ubuntu 11.04，一个Ubuntu 12.04。 然而由于硬盘比较小，最近一年多里已经屡次因为硬盘空间不够而发生这样那样的问题。这次也是一样。这次我是把我的C盘空间用EASEUS Partition Master 8.0.1调大了一点，以使C盘不再一直处于空间不够的警告，结果重启Windows之后就出现错误： error: incompatible license. Entering rescue mode… grub rescue> 我非常明白这是由于硬盘序列ID变了才导致GRUB无法工作。一开始我以为用正常的grub-update就可以搞定（grub rescue下手动启动的方法可参考下面的附录），结果不然。 于是俺使劲的找，终于找到了 正确的方法： GET BOOT-REPAIR: Three possibilities to get Boot-Repair: 1) Boot-Repair-Disk is the official CD containing the very last version of […]
WIN7下调整C盘分区大小后：error: incompatible license.
虽然NDK编译ffmpeg的文章在网上已经多如牛毛，但还是经常有人在群里反反复复的问android怎么编译ffmpeg？这个不行，那个不行。。。 我之前也写过两篇关于NDK编译ffmpeg的文章，但基本上写了一大堆的步骤，统统被人无视，为什么？因为大家都很懒，懒得去管那一堆的这个那个步骤。只希望直接拿到所有的源码，然后打一个命令一次性搞定。 好吧，既然大家都这个想，那我就搞一个出来，但还是会有几个“烦人的”步骤： 先交待一下编译环境： 1. Ubuntu 11.04（任何一个发行版都OK） 2. NDK：当前最新的ndk-r8d 具体步骤： 1. 下载ffmpeg for android补丁。这个补丁我是放在我的一个svn服务器上的，所以你需要安装一个svn客户端，RapidSVN, RabbitVCS等都可以，然后checkout https://svn.rg4.net:8443/svn/ffmpeg/（有人回报说一直用TortoiseSVN会一直报需要用户名密码才能check out，如果碰到这种情况请用ustcer/ustcer登录） 2. 下载ffmpeg源码0.11.2(Happiness)，虽然现在最新版的ffmpeg已经到1.1.2(Fire Flower)了，但很不幸，0.11.2是当前最后官方支持android的版本（非官方的有很多，最新版本也都可以编译，但用于正式产品，…我不 知道），你暂时不用费力去找了，因为我刚刚已经“费过力”了。ffmpeg下载地址：http://ffmpeg.org/download.html 3. 将步骤2下载到的ffmpeg解开，替换到步骤1的目录下 4. 重新更新ffmpeg for android补丁（因为步骤3已经用原版的ffmpeg 0.11.2的源码覆盖了补丁，这一步是为了将补丁再次打上），将所有冲突的文件给Revert掉。 5. 打开一个terminal，进入ffmpeg补丁目录，到ffmpeg这一层，然后在此： a. 执行config.sh（若是你的ndk目录跟我不一样，请先修改config.sh中最上面的两个设定的路径，相关设定可参考下面的附录） b. 执行完成后，打开config.h，找到其中的#define restrict restrict，将其改为#define restrict，并保存退出。 c. 执行ndk-build。 完工。 附录 1. NDK路径设定说明： 这里包括两个部分： a. 路径位置 我的android SDK及NDK都是放置在/opt/google这个目录下的，完整路径为： SDK:/opt/google/sdk NDK:/opt/google/ndk-r8d […]
ffmpeg for android 编译
年关临近，又得开始准备年终总结了，我先简单罗列一下，以便写总结的时候有个参考（仅限于产品部分）。 元旦之后一个多星期又开始搞Hermes相关的一些功能，但是说实在的，我对此真的不太积极，而这主要的原因是在于，我认为（一直认为）这并不是“走在一条正确的道路上”，而且，I don’t in charge of this product。 众所周知，STUNT相对于STUN及成功率是相当的低，而且相对来说，中间流程控制起来会更加的麻烦。但是事实上，虽然我在项目周会或者其他多种场合说 明和强调，Hermes却一直在沿着这条我“个人”认为不正确的道路上走下去，而且越走越远，甚至开始衍生出其他许多这样那样的“花头”来，如： 1. 为节省打洞，把原来两开的两种socket（一种用于信令及控制，一种用于视频的传输）进行合并，以复用socket。 2. Tunnel 这如果是在其他“环境”下，可能直接就被枪毙了，可是，我们已经花了很多人力来朝着这个方向来做基于这么一个思想的东西。不对，不是一个，而是很多个衍生 产品。当然，需要去做这些衍生产品，以及这么急着在这个不确定的、甚至明知很滥的也不可能规模化的基础上去做的原因很大一部分是在于市场的需要，或者说是 那些Board members的要求。 可这实在是让人受不了了，再加一句我“个人”的见解，这些东西即使做出来到头来很多做法也都最终会被推翻掉的，再过阵子，大家回头来看这堆东西，说不定就会称之为“垃圾”，在一个宝贵的时间里做出来的“宝贵”的垃圾。可是，你又能怎么办呢？ 我先来数一数这N宗罪（不仅限于Hermes，所以题目也要改一下）。虽然在各种场合，我已经说了太多遍了，但也许我也还是得再说。 第一宗罪：似乎天下只有TCP，没有UDP。 从绑定单一的8000端口，到程序的实现，无一不是朝这个方向去做。 第二宗罪：太多的历史包袱，每个版本都在版本兼容性上花费一极大的力气，却导致许多规划、计划都无法实施。 在iNVR/eLook项目上，其实我一开始是有很多改善的措施，并且相当一部分的功能都已经实现，但由于要兼容各种旧版本的客户端，并且要兼容Windows的各种产品，结果后来又费力把已经实现好的功能拿掉，改成跟 第三宗罪：又想提升打洞成功率，又不想花时间去研究UDP及STUN的解决方案。 虽然说，其很大一部分原因是因为其他项目一直delay，但是既然Hermes项目一直在推进，为什么就不能优先去把Hermes的路给走对了呢？ 未完，待续。想起来再补充。
Hermes 之TCP及STUNT N宗罪
Network servers are traditionally implemented using a separate process or thread per connection. For high performance applications that need to handle a very large number of clients simultaneously, this approach won’t work well, because factors such as resource usage and context-switching time influence the ability to handle many clients at […]
How to use epoll? A complete example in C
元旦过后我就开始准备自己搞一个epoll的封装库，以期扔掉这个无比庞大的boost（对x86的服务器系统来说是还ＯＫ，但对一些嵌入式的应用来说，实在吃不消）。 但是始终卡在client端socket关闭后，server端针对broken pipe的signal（多线程中的signal）的处理上，这个问题一拖就拖了将近一个星期，实在汗顔。 后来实在有点火了，就准备照boost asio来扒一个下来，结果，扒着扒着发现asio原来完全可以独立于boost来运行（作为一个独立的library）。 这下真的搞的火大了。ＯＭＧ，我又浪费了将近一周的生命… 以下是来自asio作者Christopher Kohlhoff对asio与boost.asio的区别说明： Asio and Boost.Asio Asio comes in two variants: (non-Boost) Asio and Boost.Asio. The differences between the two are outlined below. What are the differences in the source code? Where do I get a release package? Where are the source code repositories? How […]