着色问题 问题分析 假设地图共有7个区域，分别是A/B/C/D/E/F/G，对上面顺序进行编号，每个区域用一个结点表示，相邻的区域有连线，那么地图就转化成一个无向连接图。 算法设计 定义问题的解空间。图的m着色问题解空间形式为n元组{x1,x2,...,xi,...,xn}，每个分量取值为1,2,3,...,m，即问题的解是一个n元向量。由此可得，问题的解空间为{x1,x2,...,xi,...,xn}，其中显约束为xi=1,2,...,m。 确定解空间的组织结构：一颗满m叉树，树的深度为n。 搜索解空间 约束条件…

回溯法 回溯法的思想是：能进则进，进不了换，换不了退。 隐约束指对能否得到问题的可行解和最优解做出的约束。隐约束包括约束函数和限界函数。 关键步骤是： 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…

题目1 二维数组中的查找 题目描述 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 题目解析 其实这个题目是非常有规律的，所以才可以用复杂度更小的方法来实现。由于其每行自左向右递增，每列自上而下递增，所我们可以设置一个初始位置，让他不在(0,0)的位置，而是第一列最后一个位置，如果实际数比它大了，那就向右查找，否则向上查找。 代码 bool Find(int target…

用动态分析解决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}， …