蛮力法常用的方案：搜索所有的解空间，搜索所有路径，直接计算，模拟和仿真，使用时可以添加一些技巧。   示例1：求所有的三位数，它除以11所得的余数等于它的三位数字的平方和 技巧：除以11的余数（除了0）只有10种可能，三个数平方和小于等于10的必定都小于等于3   示例2：字符串匹配 以文本中的每一个字符为开始字符，用模式串去匹配，直到文本结束   示例3：最近对问题 求出每两个点之间的距离，选出最小的 时间复杂度O(n^2)   示例4：凸包问题 凸集合：对于平面上的一个点集合，如果以集合中任意两点P和Q为端点的线段都属于该集合，则这个集合是凸的 凸包：一个点集合S的凸包是包含S的最小凸集合（如果S是凸的，它的凸包是它本身） 凸包定理：任意包含多于两个不共线点的集合S的凸包肯定是以S中某些点位顶点的凸多边形 凸包问题：为一个包含n个点的集合构造凸包的问题 极点：凸包的顶点 如何找到极点以及他们的连接顺序？ 遍历所有的点对，如果其他点都在这两点构成线段的一边，他们又是所有符合条件的线段的端点，则这两点是极点 提示：坐标平面上穿过(x1,y1)(x2,y2)两点的直线：(y2-y1)x+(x1-x2)y-x1y2+y1x2=0 拓展：线性规划问题（最优解一定出现在凸包的某个极点上，转换为求凸包极点的问题。） 时间复杂度O(n^3)   示例5：旅行商问题TSP 有一个旅行商从城市1出发，需要到城市2，3……n去推销，最后返回城市1，若任意两个城市之间的距离已知，求该旅行商的最佳行走路线。 TSP本质上是最小哈密顿回路：对图的每一个点经过一次最后回到原点的路径 将哈密顿回路定义为n+1个相邻顶点vi0,vi1,……vin-1,vi0的一个序列，中间n-1个顶点不相同，假设所有贿赂都开始和结束于相同的特定顶点，通过生成n-1个中间城市的组合来得到所有的旅行路线，计算这些路线的长度，然后求得最短路径。 拓展： 经过的最长距离最短 总行程与总收益的比最小 多个旅行商使得所有城市至少被访问一次，所有人的总路程最小 （回溯法，分支界限法）   示例6：背包问题 给定n个重量为w1,w1,……wn，价值为v1,v2……vn的物品，一个承重为W的背包，求这些物品中能够装到背包中的一个最有价值的子集。 找到给定的n个物品集合的所有子集，计算每个子集的总重量，然后找到其中价值最大的子集。 拓展： 完全背包：每一件物品不限件数 多重背包：每一个物品对应有一个确定的件数 （回溯法，分支界限法）   示例7：分配问题 将n个任务分配给n个人执行，每个人只执行一个任务，每个任务只能给一个人执行，将第j个任务给第i个人执行的成本是C[i,j]，求总成本最小的分配方案。 用成本矩阵C表示，问题要求在矩阵的每一行中选出一个元素，他们属于不同的列，且元素的和是最小的。 用一个n维元组来描述分配问题的一个可能的解，第i个分量表示在第i行中选择的列号，生成1,2……n的所有排列，然后把成本矩阵中相应元素相加求得每种分配方案的总成本，最后选出具有最小和的方案。 （匈牙利算法：构造成本矩阵，每行，每列减去最小值）