回溯法 回溯法的思想是：能进则进，进不了换，换不了退。 隐约束指对能否得到问题的可行解和最优解做出的约束。隐约束包括约束函数和限界函数。 关键步骤是： 1. 定义解空间； 2. 确定解空间的组织结构（子集树、排列数、m叉树等）； 3. 搜索解空间。 回溯法阶梯的关键是设计有效的显约束和隐约束。 大卖场购物（0-1背包问题） 问题举例 每个物品重量w和价值v如下表所示，购物车容量为W，求不超过购物车重量的最大价值。 w[] 1 2 3 4 2 5 4 2 w[] 1 2 3 4 6 3 5 4 问题分析 解空间={x…

用动态分析解决0-1背包问题 有n个物品，每个物品的重量为w[i]，价值为v[i]，购物车容量为W。选若干个物品放入购物车，在不超过容量的前提下使获得的价值最大。 问题分析 （1）分析最优解的结构特征 （2）建立具有最优值的递归式 可以对每个物品依次检查是否放入或者不放入，对于第i个物品的处理状态：用c[i][j]表示前i件物品放入一个容量为j的购物车可以获得的最大价值。 不放入第i件物品，xi=0，装入购物车的价值不增加。那么问题就转化为“前i-1件物品放入容量为j的背包中”，最大价值为c[i-1][j]。 放入…

最优三角剖分 与矩阵连乘的不同点 不同点就在于递归公式的不同，最优三角剖分的递归公式如下： 当i=j的时候，m[i][j]=0； 当i<j的时候，m[i][j]=min{m[i][k]+m[k+1][j]+w(v(i-1)vkvj)} 图解示例 我们以一个凸多边形为例，其每条边的权重如下表所示 g[][] 0 1 2 3 4 5 0 0 2 3 1 5 6 1 2 0 3 4 8 6 2 3 3 0 10 13 7 3 1 4 10 0 12 5 4 5 8 13 12 0 3 5 6 6 7 5 3 0 （…

关于最长公共子序列（LCS） 最长公共子序列和最长公共子串是有区别的，之前我一直把它们混淆。 最长公共子串举例：假设S1={A,D,C,B,E,X,Q}，S2={H,P,D,C,B,E,M,L} 那么它们的最长公共子串就是{D,C,B,E}。这是我通常理解的东西。 最长公共子序列。 最长公共子序列举例：假设S1={A,B,C,A,D,A,B}，S2={B,A,C,D,B,A}，那么它们的LCS就是{B,A,D,B}。 求解最长公共子序列 这是一个动态规划问题。如何求解最长公共子序列（以下用LCS代替）呢？我们假设已…

题目1 滑动窗口的最大值 题目描述 给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， …

Dijkstra算法 待后续补充 哈夫曼编码 1.算法介绍 哈夫曼编码采取的贪心策略是每次从树的集合中取出没有双亲且权值最小的两个树为左右子树，构造一棵新树，新树根结点的权值为其左右孩子的结点权值之和，将新树插入到树的集合之中。 求解步骤如下： （1）确定合适的数据结构，编写程序前要考虑： ①哈夫曼树中没有度为1的结点，则一棵有n个叶子结点的哈夫曼树共有2n-1个结点（n-1次合并，每次产生一个结点）； ②构成哈夫曼树后，为求编码，需从叶子结点除法走一条从叶子到根的路径。 译码需要从跟除法走一条从根到叶子的路径，那…

从头到尾彻底理解KMP 作者：July 原文地址：http://blog.csdn.net/v_july_v/article/details/7041827