第1章 蛮力法.pptVIP

* 第1章 蛮力法 1. 穷举理论 2. 穷举工具 3. 穷举法举例 1. 穷举理论 穷举法，或者称为蛮力法，是一种直接、简单的用计算机解决问题的方法 计算机的产生使得穷举法有了更多的用武之地。例如，4色问题的证明 穷举法的计算时间性能往往是最低下的 穷举法是基础；穷举法可以用于解决某个问题的一个或几个阶段或部分；穷举法的设计能够加深对问题的了解 2. 穷举工具 2.1 因地制宜的工具 2.2 组合工具 2.3 排列工具 2.4 进制工具 2.1 因地制宜的工具 许多简单的问题可以根据题目提供的条件设计穷举算法，这些算法没有通用的设计方式，通常是一重或多重循环 例如，求一个没有排序的整数数组中的最大元素值或最大元素位置 又例如，在一个没有排序的整数数组中查找给定的一个整数值所在的位置（查找不成功则返回-1） 2.2 组合工具 组合工具用于解决组合穷举问题。抽象为0~(n-1)的n个数中取m个 组合工具是一个类CCombination，内部结构是一个数组，对外接口是一个BOOL next()函数 组合工具的BOOL next()函数把当前数组内容按照字典序求得下一个数组内容 next()函数设计：从右向左，找到第一个不存有自己最终内容的位置。把这个位置上的数值加1，后面的数值递增 0 1 2 0 1 3 0 1 4 0 2 4 2 3 4 … 2.3 排列工具(一) 排列工具用于解决组合穷举问题。抽象为0~(n-1)的n个数中取m个并排列 排列工具是一个类CPermutation，内部结构是一个数组，对外接口是一个BOOL next()函数 排列工具的BOOL next()函数把当前数组内容按照字典序求得下一个数组内容。下例5排列3 2.3 排列工具(二) 排列工具的BOOL next()函数构造办法： 首先，确定某个位置是否已经达到了当前意义下的“最大值”—“当前” 的意义：前面的位置数值固定之后 然后，从后向前寻找第一个不是当前最大值的位置 这个位置上的数值最小限度地增加—“最小限度”，前面的数值排除之后，取剩余的、大于该值的最小值 该位置确定后，后面的位置依次取剩余数值的最小几个 1 3 2 未达到 未达到 未达到 1 3 4 0 2 4 1 4 0 … 4 3 2 2.4 进制工具（一） 进制工具来源于k进制数。 k进制从小到大排列（位数不足补0）时，数字呈现字典序。例如，000, 001, 010, … 111。又例如，000, 001, 002, 010, …, 222 进制状的数据变化各个位置上的数字可以自由变化，而不像排列组合一样，受到其他位置上的制约 进制工具可以不使用类单独封装数据和方法，而是直接用数进行循环，然后在循环中解码当前循环数 2.4 进制工具（二） 例如，一列火车可以在1~N这N个车站停车。每次停车意味着可以多载顾客（不同的车站按照订单收益不同），这方面可以提高火车的效益；但停车又意味着时间的耽搁、站内费用的增加（不同的车站耗费不同），这方面使收入减少。请给出一个策略，让火车在某些站停车，使得收入最大化。 for (int i=0; i2N; i++){ 把i解码成N位二进制串 用二进制串计算此次收益情况 如果此次收益大于最大值，则保存此次停车安排 } 2.4 进制工具（三） 上述的进制情况是一种特殊情况，更普遍的情况是：共有N个元素，每个元素可以独立取值0~ni (0=iN) 这种情况下，需要进制工具—一个类—来处理遍历问题 进制工具是一个类CDigital，内部结构是一个数组，对外接口是一个BOOL next()函数 2.4 进制工具（四） 进制工具的BOOL next()函数使得内部的数组从一个状态按照字典序变化为下一个状态 具体做法：从后向前找到第一个不是该位置最大值的位置，然后把该位置数据加以即可，最后把后面的各个位置写对应的最小值 下图的3个位置依次从0~3，0~4，0~2中取值 0 0 0 0 0 1 0 0 2 0 1 0 …… 1 4 2 2 0 0 …… 3 4 2 2 0 1 3. 穷举法举例 3.1 最大子段和问题 3.2 找钱问题 3.3 背包问题 3.4 TSP问题 3.5 n皇后问题 3.6 假币问题 3.7 凸包问题 3.8 查找问题 6.9 排序问题 3.10 多段最短路径问题 3.11 任务分配问题 3.12 气球膨胀问题 3.1 最大子段和问题 给定n个整数（可以是0、可正、可负）组成的序列a1, a2, …, an, 求该序列形如 的子段和的最大值。 例如，当序列为{-2, 11, -4, 13, -5, -2}时，最大子段和为 如何穷举？如果采用蛮力法，上述序列共有多少种情况需要穷举？ 3.2 找钱问题 一套钱币有几种不同的面值构