算法相关部分
常考的算法是从8.3章节的分治法开始往后。
分治法：
分治法书上说的比较简单，也没有大段的好像找不到逻辑规律的文字描述，就说了分三步：
1、分解 2、求解 3、合并
特点也用一句很简洁的话说出来了：“这些子问题互相独立且与原问题相同。分治法产生的子问题往往是原问题的较小模式，这就为递归技术提供了方便。”。
---
分治法的典型实例也说了两个：第一个就是题目中所说的归并排序，明显就是这三步，完美符合分治法的特点。
第二个是最大子段和问题。也就是给一组数，问哪一段连续的数值加起来最大？和归并差不多都需要划分为最小子段，不过在比较的时候，需要考虑三种情况，1种是和整段(或分段)的前半段相同，2种是和后半段相同，3种是横跨前后两段。划分的每一段都需要进行这三种情况进行比较。
-----------------------------------
动态规划法：另一个常考的算法
说了4步：1、找到【最优解】的结构性质，2、递归定义最优解，3、计算出最优解，4、构造出最优解
算法需要的问题特点：1、有最优子结构（贪心法也可能适用），2、重复子问题，“即当一个递归算法不断地调用同一个问题时”。问题的解需要相同。
---
典型实例：
01背包问题：就是一个背包不能超过它的最大重量w，有多个物品(个数n)，物品有价值vi，和重量wi。问怎么才能让装进去的东西总价值最大？
01的意思就是要么放1个，要么不放，不能再拆分。书上的解释在428页，大段的可能不好理解的逻辑（代码形式的文字描述，而不是通常易理解的形式），直接搞代码了。如果看代码理解快的请自行查看它的详细策略。
考点：在2013、2016年的题目考过它的详细01背包问题的求解。2010、2019考过01背包的特点从属关系。
最长公共子序列：就是给两个序列，找出它们里面最长相同的相连的是哪一段。同样是利用的它的4步。
矩阵链乘问题（书上667页）。
-----------------------------------
贪心法：直接看原文吧，非常好理解：“和动态规划法一样，贪心法也经常用于解决最优化问题。与动态规划法不同的是，贪心法在解决问题的策略上是仅根据当前己有的信息做出选择，而且一旦做出了选择，不管将来有什么结果，【这个选择都不会改变】。换而言之，贪心法并【不是从整体最优】考虑，它所做出的选择只是在某种意义上的【局部最优】。这种局部最优选择【并不能保证总能获得全局最优解】，但通常能得到较好的近似最优解。”。
“如果只有面值分别为1、5和11单位的硬币，而希望找回总额为15单位的硬币，按贪心算法，应找1个11单位面值的硬币和4个1单位面值的硬币，共找回5个硬币。但最优的解答应是3个5单位面值的硬币。”
它的适用性同样有最优子结构，另一个是贪心选择性质。贪心法先要确定有一个原则，按什么最大或者最小或者最近或者最远来规划。重点是一开始的选择最怎么怎么样。
例子：同样举了两个例子，1个是活动选择问题（具体请自行查找），1个是背包问题。这个背包问题也叫部分背包问题，和上面的01背包问题不同，部分背包问题的物品还可以拆分，比如一包瓜子，可以抓一把放到背包里。这个就适合用贪心法。这个就可以按总价值最大来装，或者也可以按最小重量来装，两种不同的贪心。
另外两个算法可以看题： https://www.z21.org/question/100
书上举的例子里面，回溯法的实例也有01背包问题，另外还有一个以前可能是2019年上半年在应用题的算法中考过的n皇后问题，并且问它是什么算法，其实是回溯法。（深度优先）。
分支界限法，它的实例仍然有01背包问题。而且只举了这个实例。（广度优先）。
- 发表于 2022-05-24 01:55
- 阅读 ( 602 )
- 分类：默认分类
你可能感兴趣的文章
相关问题
- 采用Dijkstra算法求解下图A点到E点的最短路径，采用的算法设计策略是（）。该最短路径的长度是（） 1 回答
- 折半查找在有序数组A中查找特定的记录K：通过比较K和数组中的中间元素A[mid]进行比较，如果相等，则算法结束； 1 回答
- 归并排序算法在排序过程中，将待排序数组分为两个大小相同的子数组，分别对两个子数组采用归并排序算法进行排序,排好序的两个子数组采用时间复杂度为0(n)的过程合并为一个大数组。 1 回答
- 在求解某问题时，经过分析发现该问题具有最优子结构和重叠子问题性质。则适合()算法设计策略得到最优解。若了解问题的解空间，并以广度优先的方式搜索解空间，则采用的是()算法策略 1 回答
- 最大尺寸和问题描述为，在n个整数(包含负数)的数组A中，求之和最大的非空连续子数组，如数组A=(-2,11,-4,13,-5,-2)，其中子数组B=(11,-4,13)具有最大子段和20(11-4+13=20)。求解该问题，可以将数组分为两个n/2个整数的子数组最大子段或或者在前半段，或者在后半段，或者跨越中间元素，通过该方法继续划分问题，直至最后求出最大子段和，该算法的时间复杂度为() 1 回答
- 采用贪心算法保证能求得最优解的问题是（） 1 回答
