贪心法

贪心法 贪心法和分治法、动态规划一样，也属于分治策略这个大框架。先简单回顾分治法和动态规划，两者在求解子问题时，都要先解出其依赖的所有“子子问题”，然后基于此得到当前子问题的解。而贪心算法在求解子问题时，则是先做“目前看来最优的选择”，然后再求解子问题。这意味着贪心算法在不知道“子子问题”的解的情况下求出了“部分解”。那么对于原问题，除了要存在分治算法和动态规划算法(最优子结构)，还要有“更强的性质”才能有贪心算法，称为贪心选择性。 经典的(01)背包问题是没有贪心选择性质的，如果以“每次取价值最大的物品”的策略求解，得到的解可能不是总价值最大的解，并且也没有其他的贪心策略能求解。但如果背包里的物品是可分割的(这时也称为部分背包问题)，就是能取物品的2%、0.3%，那么上述贪心策略就能找到最优解，也就是说部分背包问题具有贪心选择性质，这是个很显然的结论不需要证明。这里稍微提一个细节，计算机是不好直接处理无理数小数和循环小数的，但把有理数用二元组表示就能解决这个问题，而由于解的每一项都能写成关于输入的算数表达式，所以只要输入都是有理数那么这个问题就好用计算机直接求解。… 阅读全文

活动选择问题问题可表述为“设\(S[0,1…n]\)为‘活动’的序列，每个‘活动’有开始、结束时间，\(S\)已按结束时间升序排序。规定所有‘活动’独占同一个教室，求出\(S\)中的‘活动’最多能安排多少个”。上图是其中一种\(S\)的例子。 设\(L\)是一个最优活动安排序列(已排序)。任取\(L[k]\)，并用其划分序列\(L_1 = L[0,…,k-1],L_2=L[k+1,…]\)。然后设\(s_1\)是“\(L[k]\)开始前结束的\(S\)中的所有活动”，\(s_2\)是“\(L[k]\)结束后开始的\(S\)中的所有活动”。可发现如果把\(s_1,s_2\)作为原问题的输入，则\(L_1,L_2\)必可分别作为最优活动安排序列，否则\(L\)本身就不是原问题的最优解了。然后任取\(L_1[k_1]\)……可以发现上述结论是递归的。然后用这个性质去找最优解，先回到原问题上，其任意最优活动安排序列都符合“空序列,包含\(S[0]\),包含\(S[1]\),包含\(S[2]\)…”中的至少一种，如果符合的是空序列，那么解就是0，否则就遍历这些元素，设每次遍历到的元素是\(x\)，然后用其划分\(S\)为“\(x\)开始前结束的\(S\)中的所有活动”，“\(x\)结束后开始的\(S\)中的所有活动”这两个序列，然后分别递归的求出它们的解并计做\(c_1,c_2\)，然后求出\(c=c_1+1+c_2\)，即放入\(x\)后的总活动数。每次遍历都会求一次\(c\)，其中最大的那个就是解。… 阅读全文

字符编码编码指把相同信息在不同的形式间转化，例如把图片储存为像素(x,y,r,g,b)，把直角坐标方程改写为极坐标方程，把26个字母用26个二进制数表示，把明文转为密码和密文等等。无论信息形式如何变化，它们依然是同样的信息。字符编码研究如何用二进制形式表示某种语言的字符，其可被分类为定长编码与变长编码。基础ASCII码是种定长编码，无论是英文逗号、空格、回车、换行甚至响铃都有自己的ASCII码。其定长策略是在所有二进制数(编码)前补0，保证每个编码都是7-Bit。强国官方编码GB18030是种变长编码，其有1/2/4字节三种长度，1字节长度的是ASCII的超集，2字节长度的是GBK的超集，4字节长度的是其他新加入的生僻的中文字符与中文符号。   前缀编码对任意字符串的任意前缀编码方案，每个字符的编码都不是其他编码的前缀。任何前缀编码方案都可用二叉树(如上图)表示，其非叶节点的左/右边表示0/1，从根节点出发可根据编码方案“生成”编码树。由于前缀码间互不为前缀，故字符不会出现在非叶节点，故叶节点必为被编码字符本身。对字符串\(S\)与其前缀编码二叉树\(T\)，设\(f(c)\)为字符\(c\)的出现次数，\(d(c)\)为字符\(c\)在前缀编码二叉树的深度，编码二叉树所对应的代价为\(B(T)=\sum… 阅读全文

拟阵的定义 拟阵(Matroid)一词最早于1935年被数学家Whitney使用，其是从矩阵的线性无关概念中提炼而来的，拟阵多种不同的等价定义，其基于子集系统的定义如下，第1～4定义了子集系统，拟阵是满足交换性质的子集系统： 1) 拟阵\(M\)是为二元组\((S,L)\)； 2) \(S\)是有限集合； 3) \(L\)是由\(S\)的符合下述性质的子集组成的有限非空集； 4) 遗传性质：对任意\(B\in L\)与\(A\subseteq B\)，都满足\(A\in L\)； 5) 交换性质：对任意\(A\in L\)与\(B\in L\)。若\(|A|<|B|\)，则存在\(x \in B-A\)，使\(A\bigcup\{x\} \in L\)； 在无向图\((V,E)\)上可定义图拟阵(Graphic Matroid)，图拟阵与拟阵等价，故图拟阵也可定义拟阵：… 阅读全文

问题描述 单位时间任务的最优调度问题的原型是操作系统在单核CPU上的调度，其需要的输入信息如下。问题的目标是找到\(S\)的一个调度(排序)，可以使得超过截止时间后的总惩罚值最小。 1) \(n\)个单位时间(耗费时间为1)任务的集合\(S=\{a_1,a_2…\} \)； 2) \(n\)个整数的期望的截止时间\(\{d_1,d_2…\} \)，显然\(1 \leq d_i \leq n\)； 3) \(n\)个非负的惩罚值\(\{w_1,w_2…\} \)； 在讨论问题前，预先给出更进一步的定义与相关性质如下： 1) 提前任务：任务在某个调度的截止时间前完成，称该任务为该调度的提前任务； 2) 延迟任务：任务在某个调度的截止时间后完成，称该任务为该调度的延迟任务； 3) 提前优先调度：任意调度可在总惩罚值不变时，把所有提前任务排在延迟任务前；… 阅读全文