1、概述

2、递归

3、分治法-基于递归思想

二路归并 T(n)=O(nlogn)

自底向上

自顶向下

描述一个算法 解决问题的步骤

例：

3.3.1查找最大和次大元素T=O(n)

分治法求最大和次大元素的思路可以简要概括为以下几个步骤：

1. 分解：将当前问题的数据集分成两个大小大致相等的子集.
2. 解决：递归地在两个子集中分别找到最大和次大元素.
3. 合并：
   • 比较两个子集各自的最大元素,确定整个数据集的最大元素.
   • 次大元素可能是以下几种情况之一：
     • 两个子集中较小的最大元素.
     • 两个子集中的次大元素(如果最大元素来自同一个子集).
   • 对这些候选元素进行比较,确定整个数据集的次大元素.4、直接解决：如果数据集足够小,直接通过比较操作找出最大和次大元素.
   通过这种方式,分治法将大问题分解为小问题处理,再将小问题的解合并为大问题的解,有效地减少了比较次数,提高了效率.

3.3.2折半查找T=O(logn)

折半查找(也称为二分查找)是为了解决在一个有序数组中查找特定元素的问题.其基本思路如下：

1. 初始化查找区间：设定查找区间的起始位置low和结束位置high,即a[low..high]是当前的查找区间.
2. 计算中点：首先确定该区间的中点位置mid,计算方法为mid = ⌊(low + high) / 2⌋.
3. 比较并缩小查找范围：
   • 若k == a[mid],则查找成功并返回该元素的物理下标.
   • 若k < a[mid],由于数组是有序的,可知a[mid..high]均大于k,因此如果数组中存在关键字等于k的元素,则该元素必定位于左子数组a[low..mid-1]中.因此,新的查找区间更新为左子数组a[low..mid-1].
   • 若k > a[mid],同理,要查找的k必在位于右子数组a[mid+1..high]中,因此新的查找区间更新为右子数组a[mid+1..high].
4. 重复查找：在新的查找区间内重复上述步骤,直到找到元素或查找区间为空.

通过这种方式,折半查找每次都将查找区间减半,从而大大减少了需要比较的次数,提高了查找效率.折半查找的时间复杂度为O(log n),其中n是数组的长度.

3.3.3寻找一个序列第k小元素T=O(n) 时间复杂度非常低 居然只有On 很特别！

注：这个算法在进行排序过程中比较元素与基准

类似于快排的双指针算法

分治法寻找一个序列中第k小元素的简要思路如下：

1. 选择基准：从序列中随机选择一个元素作为基准(pivot).
2. 划分：将序列划分为两个子序列,一个包含所有小于基准的元素,另一个包含所有大于或等于基准的元素.
3. 确定位置：计算小于基准的元素数量n.
   • 如果n正好等于k-1,则基准元素即为第k小元素,算法结束.
   • 如果n大于k-1,则第k小元素位于小于基准的子序列中,对该子序列递归执行上述步骤.
   • 如果n小于k-1,则第k小元素位于大于或等于基准的子序列中,对该子序列递归执行上述步骤,但是要寻找的是第k-n-1小元素.
4. 递归：根据第3步的结果,递归地在相应的子序列中查找第k小元素.
5. 终止条件：当子序列足够小或满足特定条件时,直接计算第k小元素.

通过这种方式,分治法能够有效地减少问题规模,逐步逼近第k小元素,直到找到为止

3.3.4寻找两个等长有序序列中位数Tn=O(logn)

核心思路如下

由于每个序列都是等长有序的,所以求解其中任意一个序列的中位数变得十分简单

3.4求解组合问题

3.4.1求解最大连续子序列和问题 (分治法解决)T=O(nlogn)

-2 11 -4 13 -5 -2

对比动态规划只需要O(n),动态规划往往时间复杂度低,但空间复杂度高

使用分治法解决最大连续子序列和问题的思路是将序列分成两个子序列,分别求解左半部分和右半部分的最大子序列和,然后再找出跨越两个子序列的最大子序列和,最后这三者之中的最大值即为整个序列的最大子序列和.具体步骤如下：

1. 分解：将序列从中间分成两个子序列.
2. 递归求解：
   • 递归地求解左半部分的最大子序列和.
   • 递归地求解右半部分的最大子序列和.
3. 合并：
   • 找出跨越左右两个子序列的最大子序列和.这需要从中间向左遍历找出最大子序列和,再从中间向右遍历找出最大子序列和,最后将这两个和相加.
   • 将上述三个和(左半部分的最大子序列和、右半部分的最大子序列和、跨越两个子序列的最大子序列和)中的最大值作为整个序列的最大子序列和.
4. 递归终止条件：当序列只包含一个元素时,返回该元素(如果该元素为正)或0(如果该元素为负),因为最大子序列和不会小于0.

分治法解决这个问题的时间复杂度是O(n log n),因为每次分解将问题规模减半,每层递归需要线性时间合并结果.

3.4.2求解棋盘覆盖 略

3.4.3循环日程安排 略

3.5.1求解大整数乘法 优化的karatusba算法Tn=O(n^1.59)稍复杂

分治法求解大整数乘法问题通常采用Karatsuba算法.这个算法基于分治思想,将大整数乘法问题分解为更小的子问题,从而减少了乘法操作的次数.Karatsuba算法的基本思路如下：

1. 分解：假设有两个大整数X和Y,我们可以将它们分别分解为两部分.例如,X = A * 10^n/2 + B,Y = C * 10^n/2 + D,其中A和C是高位部分,B和D是低位部分,n是数字的长度(假设X和Y长度相同,如果不同可以在前面补零).
2. 递归求解子问题：按照普通乘法,我们需要计算四个乘积：AC,AD,BC,和BD.Karatsuba算法通过减少乘法次数来提高效率,只计算三个乘积：
   • AC
   • BD
   • (A + B) * (C + D),然后从中减去AC和BD,得到AD + BC.
3. 合并结果：根据上述三个乘积,我们可以得到最终结果：X * Y = AC * 10^n + (AD + BC) * 10^n/2 + BD.
4. 递归终止条件：当整数足够小,不再适合分解时,直接使用普通乘法计算.

Karatsuba算法的时间复杂度是O(n^log2(3))或约O(n^1.585),相比于普通乘法的O(n^2)有显著提高.这个算法之所以有效,是因为它通过减少乘法操作的次数来减少计算量,特别适用于大整数的乘法计算.

3.5.2矩阵乘法Tn=O(n^2.81)太复杂了 略

分治法求解矩阵乘法问题通常指的是Strassen算法.这个算法通过减少矩阵乘法中的乘法操作次数来提高效率.传统的矩阵乘法需要8次乘法操作,而Strassen算法将其减少到7次.基本思路如下：

1. 分解：将每个矩阵分成四个子矩阵.对于两个n x n的矩阵A和B,可以分别将它们分解为四个n/2 x n/2的子矩阵.即：
   • A = [A11 A12; A21 A22]
   • B = [B11 B12; B21 B22]
2. 递归求解子问题：计算7个矩阵乘法(而不是8个),这些乘法操作定义如下：
   • M1 = (A11 + A22) * (B11 + B22)
   • M2 = (A21 + A22) * B11
   • M3 = A11 * (B12 - B22)
   • M4 = A22 * (B21 - B11)
   • M5 = (A11 + A12) * B22
   • M6 = (A21 - A11) * (B11 + B12)
   • M7 = (A12 - A22) * (B21 + B22)
3. 合并结果：使用上述7个乘积来计算最终的矩阵乘法结果的四个子矩阵：
   • C11 = M1 + M4 - M5 + M7
   • C12 = M3 + M5
   • C21 = M2 + M4
   • C22 = M1 - M2 + M3 + M6
4. 递归终止条件：当子矩阵足够小,不再适合分解时,直接使用普通矩阵乘法计算.

Strassen算法的时间复杂度是O(n^log2(7))或约O(n^2.81),相比于普通矩阵乘法的O(n^3)有显著提高.这个算法之所以有效,是因为它通过减少乘法操作的次数来减少计算量,特别适用于大规模矩阵的乘法计算.然而,由于Strassen算法在实际计算中可能引入更多的舍入误差,对于需要高精度计算的应用场景,需要仔细考虑是否使用.

并行计算不用看

4、蛮力法

不讲时间复杂度的不看

4.2.4最大连续子序列和T(n)=O(n)优化优化从n³到n²到n已经是动态规划，不再是蛮力

最暴力的O(n^3)蛮力法求解最大连续子序列和的思路：

1. 初始化最大和maxSum。
2. 遍历数组，确定每个元素作为子序列起点。一重
3. 对于每个起点，再次遍历数组，确定子序列的终点。 二重
4. 对于每个起点和终点确定的子序列，遍历这个子序列，计算子序列的和thisSum。 三重
5. 更新maxSum为thisSum和maxSum中的较大值。
6. 重复步骤2到5，直到所有可能的起点和终点的子序列都被考虑过。
7. 返回maxSum作为最大连续子序列和。

---

优化到O(n^2)的蛮力法求解最大连续子序列和的思路：

1. 初始化最大和maxSum。
2. 遍历数组，确定每个元素作为子序列起点。
3. 从每个起点开始，逐步扩展子序列到数组末尾，同时计算并更新这个子序列的和thisSum。
4. 对每个子序列，更新maxSum为thisSum和maxSum中的较大值。
5. 重复步骤2到4，直到遍历完所有元素作为起点的情况。
6. 返回maxSum作为最大连续子序列和。

课堂练习不看

4.2.5求解幂集 T(n)=O(n*2ⁿ) 暴力到指数级时间复杂度

暴力法求解幂集问题的思路：

1. 首先，确定幂集的大小。对于包含n个元素的集合，其幂集包含2^n个子集（包括空集和自身）。
2. 使用一个外层循环遍历从0到2ⁿ-1的所有整数。每个整数代表一个可能的子集，其中整数的二进制表示中的每一位对应集合中的一个元素。位为1表示该元素在子集中，位为0表示该元素不在子集中。
3. 对于每个整数，使用一个内层循环遍历其二进制表示的每一位。如果某位为1，则将对应的元素添加到当前子集中。
4. 对每个整数，内层循环结束后，你会得到一个子集。将这个子集添加到幂集中。
5. 重复步骤3和4，直到所有整数都被遍历。
6. 返回幂集。

这种方法直接枚举了所有可能的子集，因此是一种暴力解法。

外层遍历2ⁿ,内层有n

4.2.6 0/1背包可能性不大 略

4.2.7全排列问题 T(n)=O(n*n!) 很蠢 带有回溯的思想

采用插空的蛮力法来求解全排列问题的思路是，对于每个元素，我们在当前排列的所有可能位置上尝试插入该元素。这种方法的关键在于，对于每个新元素，我们都尝试将其插入到已有排列的所有可能位置（包括排列的开头、所有元素之间的空隙，以及排列的末尾），然后对每种可能的新排列递归地重复这个过程，直到所有元素都被插入。

以下是这个思路的实现步骤：

1. 递归函数定义：定义一个递归函数，该函数接受当前排列（初始时为空）、待插入的元素集合和结果集合作为参数。
2. 终止条件：如果待插入的元素集合为空，则将当前排列添加到结果集合中，因为这意味着所有元素都已经被成功插入。
3. 递归和回溯：对于待插入的元素集合中的每一个元素，尝试将其插入到当前排列的所有可能位置。对于每一种插入方式，更新当前排列和待插入的元素集合，然后递归调用自身。完成递归调用后，进行回溯，恢复当前排列和待插入的元素集合的状态，以便尝试下一个元素的插入。

这也有回溯，不然实现不了啊

4.2.8任务分配问题 略

4.3递归在蛮力法中的应用 稍微看看(no)

4.4图的深度优先广度优先遍历

深度优先

广度优先

深度与广度优先在思路上的重要区别是，深度是访问其中一个点的时候继续深度优先，广度是访问完1到n所有点后再从1到n每个依次广度优先

---

最短路问题 单源最短路 Dijkstra算法 bellman算法

最小生成树Kruskal Prim

4.4.4迷宫稍微看看(no)

5、回溯法-基于递归思想

深度优先思想+剪枝

而回溯法更多用于寻找所有可行解.

子集树 排列树？

剪枝函数很重要

一、解空间为子集树

5.3求解幂集 回溯法 草你吗的子集树求解步骤

这个图有错

输出1，3的时候显然错了，应该是dfs[1,0,1] 太明显了 这个很好理解

5.4插入符号让结果为100 (没有写出详细步骤的不看)(看看即可)

二、解空间为排列树

5.5 元素全排列 必考必看

回溯法求解全排列问题的排列树是一个递归构造的过程，其中每个节点代表了一个决策步骤。以下是绘制排列树的详细过程，以元素集 {1, 2, 3} 为例：

1. 根节点：根节点是空的，表示还没有做出任何选择。
2. 第一层节点：从根节点出发，每个子节点代表选择了一个不同的元素作为排列的第一个元素。对于 {1, 2, 3}，这意味着根节点会有三个子节点，分别代表选择了 1、2、3 作为排列的开始。
3. 第二层节点：对于每个第一层的节点，再次进行选择，但这次不能选择已经被选择的元素。例如，如果第一层选择了 1，那么第二层的节点就代表选择 2 或 3 作为排列的第二个元素。
4. 第三层节点：继续这个过程，直到所有元素都被选择。每个叶节点代表了一个完整的排列。
5. 绘制：从根节点开始，按层绘制每个决策节点，使用线连接父节点和子节点，以表示决策的流程。

以下是具体的绘制步骤：

根节点

│

├── 1

│ │

│ ├── 2 → 3 (完成一个排列：1 2 3)

│ └── 3 → 2 (完成一个排列：1 3 2)

│

├── 2

│ │

│ ├── 1 → 3 (完成一个排列：2 1 3)

│ └── 3 → 1 (完成一个排列：2 3 1)

│

└── 3

│

├── 1 → 2 (完成一个排列：3 1 2)

└── 2 → 1 (完成一个排列：3 2 1)

• 每个节点表示一个决策点，节点上的数字表示选择了哪个元素。
• 箭头 → 表示决策的方向，指向下一个选择的元素。
• 每个从根节点到叶节点的路径代表了一种完整的排列。

通过这种方式，你可以清晰地看到回溯法是如何逐步构建出所有可能的排列，并形成一个决策树的。这个树状结构帮助理解算法的执行流程，以及如何通过回溯来撤销选择，从而探索所有可能的排列组合。

感觉还是简单

5.1.4回溯法与深度优先遍历的异同 bikao

同： 实现上遵循深度优先 一步一步往前探索

异：

1、目的（访问序不同）

DFS强调 遍历 本质无序

回溯强调求解过程 本质有序

2、访问节点次数不同

DFS 访问过的节点不再访问

回溯 访问过的还可能再访问

3、剪枝不同

DFS一般不考虑剪枝

回溯为了解决问题常涉及剪枝

5.2回溯法求解0/1背包 重点 重量恰好为W 重量不超过W 基本必考时间复杂度 O(2ⁿ)

先按照v/m把所有物品重新排列一次，这样可以简化子集树的样子

要少一层

画树 画出剪枝后的版本

子集树 左剪枝 右剪枝是什么

1、装入背包重量和恰好为W

简单

先说怎么画解空间树

首先确定为子集树，不涉及排列的东西

定义如下东西：totalWeight总重量 totalValue总价值 weight[i]第i个物品重量 value[i]第i个物品价值 remainWeight=weight[i]+weight[i+1]+…+weight[n]剩余总量

剪枝条件：

左剪枝：仅考虑保留totalWeight+weight[i]≤W的左孩子节点

右剪枝 仅考虑保留totalWeight+remainingWeight-weight[i]≥W的右孩子节点

然后从上到下 根节点(totalWeight,totalValue,remainingWeight)从 i=0start 左1 右0 考虑选不选第i个物品

2、装入背包重量和不超过W O(2ⁿ) 右剪枝多了一个上界函数而已 仅此而已

左剪枝不变

左剪枝：仅考虑保留totalWeight+weight[i]≤W的左孩子节点

右剪枝变为 用上界函数进行剪枝 仅保留bound(i,tw,tv)>maxv的右孩子节点

这个maxv是基于深度优先动态更新出来的 先要从左侧深挖 一直深挖

先把物品value/weight计算出来 然后重新建表

i	No	weight	value	value/weight
1	3	2	3	1.5
2	2	3	4	1.33
3	4	1	1	1
4	1	5	4	0.8

描述左剪枝条件 仅考虑totalWeight+weight[i]≤W的左孩子

右剪枝 仅考虑 bound(i,totalWeight,totalValue)≥maxv的情况 还是要取等 不然可能舍去共同最优解

其中bound用于贪心计算后续可能达到的最大价值，maxv为当前已知的最高价值情况

然后绘图

5.3 简单装载 重点中的重点T=O(2ⁿ)

复杂装载 不看

乍一看 似乎比0/1背包还撇脱

重量和不超过但要尽可能接近W

1. 初始化：设置最大重量maxw为0，当前重量cw为0。
2. 递归函数定义：定义一个递归函数tryLoad(i, cw)，其中i表示当前考虑的集装箱编号，cw表示当前的总重量。
3. 递归终止条件：如果i等于n（所有集装箱都考虑完毕）或者cw等于W，则更新maxw为max(maxw, cw)，并返回。
4. 递归选择：
   • 选择装载：如果将当前集装箱i装上不超过载重量W，则递归调用tryLoad(i+1, cw+wi)。
   • 选择不装载：无论当前集装箱是否装载，都可以选择不装载当前集装箱，递归调用tryLoad(i+1, cw)。
5. 回溯：在每次递归调用后，无需显式回溯，因为cw和i的值在每次递归调用时都是独立的。
6. 启动递归：从第一个集装箱开始，调用tryLoad(0, 0)。

说清楚 然后左右剪枝说清楚 开干

i	wi
1	5
2	2
3	6
4	4
5	3

左剪枝：只考虑totalWeight+weight[i]≤W的情况

右剪枝：只考虑totalWeight+remainingWeight[i]-weight[i]≥maxv的情况

5.4求解子集和问题T(n)=O(2ⁿ)

给一个大正整数集合和一个数，从大集合中找子集使其中元素和为这个数

易，剪枝也易 不如背包问题和装载问题

判断子集和问题有没有解 把解的情况算出来即可 如果大于0肯定有解

n皇后问题 不会很复杂 略看 时间复杂度为O(nⁿ)

图着色 略

任务分配 重点？ 其他算法涉及到过 回溯法子集树时间复杂度O(n!)

人员	任务**1**	任务**2**	任务**3**	任务**4**
1	9	2	7	8
2	6	4	3	7
3	5	8	1	8
4	7	6	9	4

简要思路

1. 初始化：定义一个n×n的成本矩阵，其中n是任务（或工人）的数量，矩阵中的元素表示完成任务的成本。
2. 选择：从第一个任务（或工人）开始，为每个任务选择一个工人（或为每个工人选择一个任务），确保每个任务只被分配给一个工人，且每个工人只被分配一个任务。
3. 约束：确保当前的分配不违反约束条件，即每个任务只能分配给一个工人，每个工人只能获得一个任务。
4. 目标：计算当前分配方案的总成本，尝试找到成本最低的分配方案。
5. 回溯：如果当前分配不是最优的或存在更好的分配方案，则回溯到上一步，尝试不同的分配方式。
6. 终止条件：当所有任务都被分配且没有更好的分配方案时，算法结束。

如何画出子集图

子集图是一种树状结构，用于表示所有可能的分配方案。每个节点代表一个分配决策，树的每一层代表一个任务的分配。根节点是空的，表示还没有任务被分配。每个节点有n个子节点，代表将当前任务分配给n个不同工人的选择。

1. 根节点：开始时，根节点为空，表示没有任务被分配。
2. 第一层节点：从根节点出发，生成n个子节点，每个子节点代表第一个任务分配给不同工人的情况。
3. 后续层节点：对于每个已有的节点，再生成n个子节点，每个子节点代表在前一个任务的分配基础上，将下一个任务分配给不同工人的情况。
4. 叶节点：当所有任务都被分配后，到达叶节点。叶节点代表一种完整的任务分配方案。
5. 剪枝：在生成子集图的过程中，如果某个分配方案的当前总成本已经超过已知的最低成本，则可以停止进一步扩展该节点，这称为剪枝，可以大大减少搜索空间。

通过这种方式，子集图展示了所有可能的任务分配方案，回溯法通过遍历这棵树来寻找成本最低的分配方案。

1. 维护当前最低成本：在搜索过程中，维护一个全局变量来记录当前找到的最低成本分配方案的总成本。
2. 计算部分成本：对于每个部分分配方案（即当前已经分配了一部分任务的方案），计算其总成本。
3. 比较成本：在每次尝试分配任务之前，估算这个部分方案完成所有任务后可能达到的最低总成本。如果这个估算成本已经超过了当前记录的最低成本，则没有继续探索这个分支的必要，因为即使这个分支的剩余任务都以最低可能成本完成，其总成本也不可能低于当前已知的最低成本。
4. 剪枝操作：基于上述比较，如果当前分支的成本超过了已知的最低成本，则放弃进一步探索这个分支，回溯到上一个决策点尝试其他可能的分配

这个剪枝方案没有给出 有些复杂，记录有最优成本 但是不算完怎么知道总成本，

活动安排问题 排列树？ 类似于后面动态规划的安排预约 ，这里目标是活动数最多

这个问题最好用贪心来做 nlogn

活动编号i	1	2	3	4
开始时间bi	1	2	4	6
结束时间ei	3	5	8	10

可以用子集树思想，每一步包含剪枝条件 感觉还不错

记录sum=活动数,endTime=上个活动结束时间 最后返回活动数最多的方案

我这么搞子集树O(2ⁿ)

排列树解法却要O(n!)

流水作业调度 重点 排列树 bound条件剪枝？

作业编号	1	2	3	4
M1时间a	5	12	4	8
M2时间b	6	2	14	7

用排列树那么时间复杂度就是O(n!)

对于有两个机器（机器1和机器2）和四项作业（记为A、B、C、D）的流水作业调度问题，其中每个作业必须先在机器1上处理，然后在机器2上处理，我们可以通过以下步骤一步一步画出排列树：

步骤1：初始化根节点

• 根节点：表示调度开始，还没有任何作业被安排。

步骤2：第一层 – 安排机器1的作业顺序

• 在第一层，我们为机器1安排作业。由于有四项作业，这一层将有4个分支，每个分支代表一项作业作为第一个在机器1上处理的作业。
• 分支：A、B、C、D

步骤3：第二层 – 继续安排机器1的作业顺序

• 对于每个第一层的节点（比如选择了A），我们为剩下的作业（B、C、D）安排在机器1上的顺序。这意味着每个第一层的节点将分出3个新的分支。
• 分支示例（如果第一层选择了A）：B、C、D

步骤4：第三层 – 继续安排机器1的作业顺序

• 对于每个第二层的节点，我们为剩下的两项作业安排在机器1上的顺序。这意味着每个第二层的节点将分出2个新的分支。
• 分支示例（如果前两层选择了A->B）：C、D

步骤5：第四层 – 确定机器1的最后作业

• 对于每个第三层的节点，只剩下一项作业未被安排，这一层将确定最后一项作业在机器1上的位置。
• 分支示例（如果前三层选择了A->B->C）：D

步骤6：机器2的作业顺序

• 由于每个作业必须先在机器1上处理再在机器2上处理，机器2的作业顺序将与机器1相同。因此，一旦机器1的作业顺序确定，机器2的作业顺序也随之确定。

完成排列树

• 通过上述步骤，我们可以得到一个完整的排列树，其中每个叶节点代表一种可能的作业调度方案。对于四项作业，总共有 (4!)（即24）种不同的排列方式。

剪枝有些离谱

不容易 略 O（n!）

6、分支限界法-基于递归思想

一般来说分支限界法跟回溯法的区别是，回溯法倾向于求解所有可能，分支限界倾向于求解最优解；

另外回溯法是基于DFS，而分支限界法更类似BFS

带比较性的要关注一下

限界函数要能写 之前是剪枝要能写写

6.2 0/1背包

No	Wi	Vi	V/W
1	16	45	45/16
2	15	25	5/3
3	15	25	5/3

6.2.1队列式分支限界法 2ⁿ

先搞清楚一件事，队列式分支限界法来求0/1背包，期待最优解 BFS思想

回溯法DFS 先得到可能解再来判断最优，所以当要求是不超过质量，右剪枝的bound函数就跟队列式分支限界很像了

i	No	wi	vi	vi/wi
1	1	16	45	分数表示
2	2	15	25
3	3	15	25

W=30 q,q1表示选择物品,q2表示不选择物品

totalWeight totalValue

w[i]

左剪枝条件

右剪枝条件 q2.upperBound≥maxv 这个maxv得到的过程是BFS 对比回溯法maxv得到过程是DFS

6.2.2优先队列分支限界法2ⁿ

出队和遍历顺序按价值优先 ，也就是说尽可能先装点，把maxv搞大，方便后续剪枝

6.3求解图的单源最短路径

单源最短路 Dijkstra是贪心 Bellman-Ford是动态规划

6.3.1队列式分支限界法时间复杂度依赖于图的样子 不确定

6.3.2 优先队列式分支限界法

注意优先队列与队列的不同！

length小的先出队，同样无法确定时间复杂度和剪枝情况

这种就很类似贪心了

模拟优先队列式分支限界法求解图单源最短路的过程跟Dijkstra算法几乎没什么两样

想想dijkstra

6.4求解任务分配问题

优先队列式求解

设置上下界函数？upperBound 和lowerBound

人员	任务**1**	任务**2**	任务**3**	任务**4**
1	9	2	7	8
2	6	4	3	7
3	5	8	1	8
4	7	6	9	4

1. 问题定义

任务分配问题（Assignment Problem）通常定义为：给定一个任务成本矩阵，其中矩阵的第 (i) 行第 (j) 列的元素表示第 (i) 个人完成第 (j) 个任务的成本，目标是将所有任务分配给所有人，使得总成本最小，且每个人只能分配到一个任务，每个任务只能被分配给一个人。

优先队列式分支限界 priorityQueue

剪枝：由于目标是求最小代价，则规定下界函数lowerBound(可能的下界，硬迭代来找) 仅拓展lowerBound≤mincost的孩子节点

x={0,0,0,0}开始，第i个任务分别由第1、2、3、4个人去干 然后画出树即可

剪枝的关键是，让没被分配的先跳出限制条件，自己寻找自己最擅长的，即使冲突，这样得到一个夸张的下界，如果这个下界还比mincost大，那肯定说不过去，就舍去

#include <iostream>

#include <vector>

#include <queue>

#include <climits>

using namespace std;

struct Node

{

int level; // 当前处理到的行（人）

int cost; // 到目前为止的成本

vector<bool> assigned; // 标记任务是否已被分配

};

// 自定义优先队列比较函数，优先级高的是成本低的

auto cmp =

{ return left.cost > right.cost; };

priority_queue<Node, vector<Node>, decltype(cmp)> pq(cmp);

// 修改后的lowerBound函数，增加输出细节

int lowerBound(const Node &node, const vector<vector<int>> &costMatrix)

{

int lb = node.cost;

int n = costMatrix.size();

cout << “计算下界，当前成本: ” << node.cost << “, 未分配任务的最小成本: “;

for (int i = node.level + 1; i < n; ++i)

{

int minCost = INT_MAX;

for (int j = 0; j < n; ++j)

{

if (!node.assigned[j] && costMatrix[i]**[j]** < minCost)

{

minCost = costMatrix[i]**[j]**;

}

}

lb += minCost;

cout << minCost << ” “;

}

cout << “, 总下界: ” << lb << endl;

return lb;

}

// 分支限界法求解任务分配问题

int solveAssignmentProblem(const vector<vector<int>> &costMatrix)

{

int n = costMatrix.size();

Node root = {-1, 0, vector<bool>(n, false)};

pq.push(root);

int minCost = INT_MAX;

while (!pq.empty())

{

Node node = pq.top();

pq.pop();

if (node.level == n – 1)

{

minCost = min(minCost, node.cost);

continue;

}

// 扩展当前节点

for (int j = 0; j < n; ++j)

{

if (!node.assigned[j])

{

Node child = node;

child.level++;

child.assigned[j] = true;

child.cost += costMatrix[child.level]**[j]**;

int lb = lowerBound(child, costMatrix);

if (lb < minCost)

{

pq.push(child);

cout << “扩展节点，成本: ” << child.cost << “, 下界: ” << lb << endl;

}

}

}

}

return minCost;

}

int main()

{

vector<vector<int>> costMatrix = {

{9, 2, 7, 8},

{6, 4, 3, 7},

{5, 8, 1, 8},

{7, 6, 9, 4}};

int result = solveAssignmentProblem(costMatrix);

cout << “最小总成本: ” << result << endl;

return 0;

}

分支限界法有趣的一点：剪枝函数设置复杂可以保证最严格的剪枝，但是计算量会增大，如果为了减少剪枝函数计算量，那么其就不会那么严格，就会导致一些无法被剪枝到 ，如何能找到一个均衡点？ 有没有最优算法能够找到最优平衡点？

6.5流水作业调度

作业编号	1	2	3	4
M**1时间a**	5	12	4	8
M**2时间b**	6	2	14	7

其中 a[j]显然是在M1上工作所需时间 b[j]是M2上工作所需时间

定义f1是M1执行完第i步的总时间 f2表示M2执行完第i步的总时间

f1+=M1[j]

f2=M2[j]+max{f1,f2}

由于要最少时间，故定义下界函数lowerBound

仅考虑lowerBound≤maxcost的节点

这个算法的下界是通过以下步骤增加的：

1. 初始下界：从当前已调度的作业序列计算的总时间。具体来说，这是通过 calculateTotalTime 函数计算的。
2. 未调度作业的最小处理时间：对于每个未调度的作业，取其在M1或M2阶段的最小处理时间，并将这些时间累加到初始下界上。
3. #include <iostream> #include <vector> #include <queue> #include <algorithm> #include <numeric> #include <limits>using namespace std;struct Job { int id; int m1Time; int m2Time; };struct State { vector<int> jobSequence; // 存储作业ID int totalTime; // 当前完成时间 int lowerBound; // 当前状态的下界 bool operator<(const State &other) const ​ { ​ return lowerBound > other.lowerBound; ​ } };// 更新calculateTotalTime函数以考虑M1和M2阶段 int calculateTotalTime(const vector<int> &jobSequence, const vector<Job> &jobs) { int m1Time = 0, m2Time = 0; for (int id : jobSequence) { const Job &job = jobs[id – 1]; // 假设作业ID从1开始 m1Time += job.m1Time; // M1阶段累加 m2Time = max(m2Time, m1Time) + job.m2Time; // M2阶段在M1完成后开始 } return m2Time; // 返回总完成时间 }// 计算当前状态的下界 int calculateLowerBound(const vector<int> &jobSequence, const vector<Job> &jobs) { vector<int> remainingJobs; for (const Job &job : jobs) { if (find(jobSequence.begin(), jobSequence.end(), job.id) == jobSequence.end()) { remainingJobs.push_back(job.id); } } // 初始下界是当前完成时间 ​ int lowerBound = calculateTotalTime(jobSequence, jobs); // 累加所有未调度作业的最短处理时间（启发式下界） ​ for (int id : remainingJobs) ​ { ​ const Job &job = jobs[id – 1]; ​ lowerBound += min(job.m1Time, job.m2Time); ​ } // 调试信息 ​ cout << “当前序列: “; ​ for (int id : jobSequence) ​ { ​ cout << id << ” “; ​ } ​ cout << ” | 初始下界: ” << calculateTotalTime(jobSequence, jobs) << ” | 增加的时间: “; ​ for (int id : remainingJobs) ​ { ​ cout << min(jobs[id – 1].m1Time, jobs[id – 1].m2Time) << ” “; ​ } ​ cout << ” | 总下界: ” << lowerBound << endl; return lowerBound; }int main() { vector<Job> jobs = { {1, 5, 6}, // 作业1 {2, 12, 2}, // 作业2 {3, 4, 14}, // 作业3 {4, 8, 7} // 作业4 }; priority_queue<State> states; states.push({{}, 0, 0}); int bestTime = numeric_limits<int>::max(); while (!states.empty()) ​ { ​ State current = states.top(); ​ states.pop(); if (current.jobSequence.size() == jobs.size()) ​ { ​ bestTime = min(bestTime, current.totalTime); ​ cout << “找到解，总时间: ” << current.totalTime << endl; ​ break; ​ } for (const Job &job : jobs) ​ { ​ if (find(current.jobSequence.begin(), current.jobSequence.end(), job.id) == current.jobSequence.end()) ​ { ​ vector<int> newSequence = current.jobSequence; ​ newSequence.push_back(job.id); ​ int newTotalTime = calculateTotalTime(newSequence, jobs); ​ int newLowerBound = calculateLowerBound(newSequence, jobs); if (newLowerBound < bestTime) ​ { ​ cout << “当前节点的下界: ” << newLowerBound << endl; ​ states.push({newSequence, newTotalTime, newLowerBound}); ​ } ​ } ​ } ​ } cout << “最佳总时间: ” << bestTime << endl; return 0; }

我感觉是很合理的 不然算不了

7、贪心法

哪些能最优？

1. 活动安排 按结束时间排序
2. 分数背包 按单位重量价值排序
3. 最优装载 按重量升序
4. 单机调度任务 类似于最优装载 最短处理时间优先
5. 哈夫曼编码 贪心策略：从权值最小的节点开始组合生成一个新节点，每次选择权值最小的两个节点
6. 流水线调度问题johnson 贪心策略：先分组， M1<=M2组A M1>M2组B 组A升序 组B降序 排序好后按序运行即可

用反证法证明最优子结构

假设存在一个最优解S’，它包含的第一个活动不是所有可选活动中结束时间最早的活动。设S是按照贪心策略选择的活动集合，其中第一个活动是所有可选活动中结束时间最早的。

如果S’是最优解，那么通过替换其第一个活动为结束时间最早的活动（如果它们不同的话），我们得到的新解S”不会比S’差。这与假设S’是唯一最优解矛盾，因为我们找到了另一个至少和S’一样好的解S”。进一步，由于贪心选择的解S在每一步都是局部最优的，且不会比任何其他解差，因此S也是全局最优解。

不一定最优

多机调度 最长过程 用最长处理时间优先可能会出问题

7.2活动安排—牵涉证明1 反证法 nlogn

贪心法解决活动安排问题的基本思想是按照活动结束时间的早晚来选择活动，具体步骤如下：

1. 将所有活动按照结束时间从早到晚排序。
2. 选择结束时间最早的活动，然后排除与该活动时间冲突的所有活动。
3. 重复步骤2，直到没有剩余活动为止。

###

步骤

1. 选择第一个活动：设活动a是所有可选活动中结束时间最早的，而活动b是最优解S’中结束时间最早的活动。根据假设，活动b的结束时间不早于活动a的结束时间。
2. 构造新的解：如果活动b不是结束时间最早的活动，我们可以用活动a替换S’中的活动b，构造一个新的解S”。由于活动a的结束时间不晚于活动b，因此所有与活动b兼容的活动也与活动a兼容。这意味着S”至少和S’一样好。
3. 迭代：对于剩下的活动，我们继续应用贪心策略，选择结束时间最早的活动。由于每次选择都不会使解变差，这保证了最终得到的解S是最优的。

反证局部最优解是全局最优解

假设存在一个最优解S’，它包含的第一个活动不是所有可选活动中结束时间最早的活动。设S是按照贪心策略选择的活动集合，其中第一个活动是所有可选活动中结束时间最早的。

• 如果S’是最优解，那么通过替换其第一个活动为结束时间最早的活动（如果它们不同的话），我们得到的新解S”不会比S’差。这与假设S’是唯一最优解矛盾，因为我们找到了另一个至少和S’一样好的解S”。
• 进一步，由于贪心选择的解S在每一步都是局部最优的，且不会比任何其他解差，因此S也是全局最优解。

结论

通过反证法，我们证明了按照结束时间最早选择活动的贪心策略能够得到活动选择问题的全局最优解。这意味着不存在比按照贪心策略得到的解更好的解，从而证明了贪心法的有效性

贪心策略：

1. 将所有活动按结束时间递增排序
2. 设S为按照贪心策略选择的活动集合，将结束时间最靠前的活动加入S，然后排除所有与之冲突的活动。
3. 重复进行步骤2，最后得到的集合S为最优解

反证法证明局部最优解也为全局最优解（最优子结构）

假设全局最优解S’的第一个活动不是结束时间最早的。用结束时间更早的活动替换S’中的第一个活动得到S”，S”不会比S’差，与S’是最优解矛盾。因此，按贪心策略得到的解S每步都是局部最优，故S也是全局最优解。

7.3背包—牵涉证明nlogn 排序占大头

分数背包问题的贪心求解策略基于每单位重量价值的最大化原则。具体步骤如下：

贪心策略

1. 计算每个物品的单位重量价值：对每个物品，计算其价值与重量的比值，即(v_i / w_i)。
2. 排序：根据每个物品的单位重量价值，将所有物品降序排序。
3. 选择：从单位重量价值最高的物品开始，尽可能多地选择每个物品。如果当前物品无法完全装入背包，则选择其可以装入的最大部分，然后停止选择。

反证局部最优解是全局最优解

假设存在一个最优解，其中包含的第一个物品不是单位重量价值最高的物品。设该最优解为S’，而按照贪心策略选择的解为S。

1. 替换：在S’中找到第一个不按照单位重量价值降序选择的物品，假设为物品A。根据贪心策略，存在另一个物品B，其单位重量价值高于A。
2. 构造新解：用物品B替换S’中的物品A（如果B的重量超过了A的重量且背包还有空间，只取B的一部分使得总重量等同于A或填满背包）。这样做至少不会降低背包的总价值，因为B的单位价值高于A。
3. 迭代：对于S’中接下来的每个选择，重复上述替换过程，直到所有选择都是按照单位重量价值降序的。

结论

通过上述替换，我们可以得到一个新的解，其价值不低于原来的最优解S’，且完全按照贪心策略选择物品。这意味着贪心策略得到的解至少和任何其他最优解一样好。因此，我们可以反证贪心策略得到的局部最优解实际上是全局最优解。

7.4最优装载nlogn 涉及排序

最优装载问题（也称为轻舟载重问题）要求在不超过船的最大承重的情况下，尽可能多地装载物品。这里的贪心策略是基于物品重量的最小化原则。

贪心策略

1. 排序：将所有物品按重量从轻到重排序。
2. 选择：依次选择重量最轻的物品装入船中，直到再也无法装下更多的物品为止。

反证贪心最优子结构

假设存在一个最优解S’，其中包含的第一个物品不是重量最轻的物品。设按照贪心策略选择的解为S。

1. 替换：在S’中找到第一个不是按照重量从轻到重选择的物品，假设为物品A。根据贪心策略，存在另一个物品B，其重量轻于A。
2. 构造新解：用物品B替换S’中的物品A。由于B的重量更轻，替换后的新解至少能装载和S’一样多的物品数量，可能还能装载更多。
3. 迭代：对于S’中接下来的每个选择，重复上述替换过程，直到所有选择都是按照重量从轻到重的顺序。

通过上述替换，我们可以得到一个新的解，其装载的物品数量不少于原来的最优解S’，且完全按照贪心策略选择物品。这意味着贪心策略得到的解至少和任何其他最优解一样好。因此，我们可以反证贪心策略得到的局部最优解实际上是全局最优解，展示了贪心选择的最优子结构特性。

7.5田忌赛马xx不看 nlogn

有点意思但比较复杂

7.6多机调度 nlogn 无法确保用贪心一定能得到全局最优

此题贪心策略是最长处理时间优先（Longest Processing Time First, LPTF）。这种策略尤其适用于当作业数量大于机器数量时，旨在尽量减少完成所有作业所需的总时间，似乎不一定能得到最优解！！！

比如 5 2 2

最优是5分钟，但是采取LPTF会导致5+2 2 =7分钟

---

另有单机调度，多个任务 一台机，要求降低平均等待时间，按照最短处理时间优先（Shortest Processing Time First, SPTF）策略，也称为最短作业优先（Shortest Job First, SJF）策略,这种容易用反证法得到局部最优解是全局最优解

---

7.7哈夫曼编码—牵涉证明 nlogn

贪心策略

1. 初始化：将字符集{d1, d2, …, dn}中的每个字符视为一个节点，并将它们的频率{w1, w2, …, wn}作为节点的权值。这些节点构成一个森林，每个节点是一棵树。
2. 构造哈夫曼树：
   • 在森林中找出两个权值最小的树作为左右子树，合并它们形成一棵新树。新树的根节点权值为其左右子树根节点权值之和。
   • 重复上述步骤，直到森林中只剩下一棵树，这棵树就是哈夫曼树。

最优子结构的证明（反证法）

假设：假设存在一种最优编码方案，其中某两个最不频繁的字符（假设为x和y，频率为wx和wy）没有在哈夫曼树中作为兄弟节点（即没有在同一次合并中被选中）。

证明：

1. 在最优编码方案中，假设x和y不是兄弟节点，那么它们必定位于树的不同深度或者相同深度但不是兄弟节点。
2. 根据哈夫曼树的构造过程，最不频繁的两个节点合并后形成的新节点的频率之和仍然是最小的，这保证了合并后的新树仍然是最优的。
3. 如果x和y不是兄弟节点，我们可以找到两个节点a和b，使得a和b是兄弟节点，并且至少有一个的频率大于或等于x和y中的一个（不失一般性，假设为x）。
4. 将x与a或b中的一个交换，使x成为a或b的兄弟节点，这样做不会增加总的编码长度，因为x的频率小于或等于a或b，而x现在位于更低的深度或相同深度。
5. 这表明原假设的编码方案不是最优的，因为我们找到了一个更优或等价的编码方案，即使x和y作为兄弟节点。

结论：这与我们的假设矛盾，因此，最优的哈夫曼编码方案中，最不频繁的字符必须在哈夫曼树中作为兄弟节点，即直接相连。这证明了哈夫曼编码的最优子结构性质。

命题1：两个最小权值字符对应的结点x和y必须是哈夫曼树中最深的两个结点且它们为兄弟。

命题1：两个最小权值字符对应的结点x和y必须是哈夫曼树中最深的两个结点且它们为兄弟。

命题2：设T是字符集C对应的一棵哈夫曼树，结点x和y是兄弟，它们的双亲为z，显然有wz = wx+wy，现删除结点x和y，让z变为叶子结点，那么这棵新树T1一定是字符集C1 = C – {x，y}∪{z}的最优树。

命题1证明

贪心思想：在构造哈夫曼树的过程中，每一步都选择两个最小权值的节点合并，以确保最终的树具有最小的加权路径长度。这是因为较小的权值如果放在较深的层次，对总的加权路径长度的贡献较小。

证明：

1. 假设在哈夫曼树中，存在两个节点x和y，它们是权值最小的两个节点。
2. 根据哈夫曼树的构造过程，每次都是选择两个最小权值的节点合并。因此，在最初的合并过程中，x和y会被首先合并，形成一个新的节点z。
3. 合并后，x和y不可能再与其他节点进行合并，因为它们已经是z的子节点了。
4. 由于每次合并都会减少一个节点，直到形成哈夫曼树，x和y作为最初合并的节点，它们在树中的位置必然是最深的。
5. 因此，x和y必须是哈夫曼树中最深的两个节点且它们为兄弟。

命题2证明

贪心思想：在构造哈夫曼树的过程中，每次选择两个最小权值的节点合并，目的是保证最终树的加权路径长度最小。删除最小权值的两个兄弟节点x和y，并将它们的父节点z变为叶子节点，相当于在字符集中替换x和y为它们的权值之和，这个操作不会影响哈夫曼树的最优性。

证明：

1. 设T是字符集C对应的一棵哈夫曼树，x和y是兄弟节点，它们的权值之和为wz。
2. 当删除x和y，将z变为叶子节点后，相当于在字符集C中替换了x和y为一个新字符z，其权值为wx+wy。
3. 在新的字符集C1中，z的权值等于x和y的权值之和，这保持了权值的总和不变。
4. 根据哈夫曼树的构造原则，合并任意两个最小权值的节点都是为了最小化加权路径长度。因此，将x和y替换为z后，对于新的字符集C1，构造出的新树T1仍然遵循了这一原则。
5. 由于每一步合并都是贪心选择最小的两个权值进行合并，因此，删除x和y后得到的新树T1对于字符集C1依然是最优的，即最小化了加权路径长度。这表明哈夫曼树的构造过程具有贪心选择性质，即局部最优选择能导致全局最优解

7.8流水线调度 johnson

解决这个流水作业调度问题的贪心策略之一是基于Johnson规则。Johnson规则适用于两台机器的情况，目标是最小化总完成时间。这个规则的核心思想是找到一种作业排序方式，使得作业在第一台机器上的加工顺序和在第二台机器上的加工顺序都尽可能地紧凑。

Johnson规则的步骤如下：

1. 对作业进行分组：
   • 将所有作业分为两个集合，集合A和集合B。
   • 如果作业i的在M1上的加工时间ai小于在M2上的加工时间bi，则将作业i归入集合A；否则，归入集合B。
2. 分别对两个集合内的作业排序：
   • 集合A中的作业按照M1上的加工时间ai升序排序。
   • 集合B中的作业按照M2上的加工时间bi降序排序。
3. 确定作业的最终加工顺序：
   • 按照集合A中的排序结果，然后是集合B中的排序结果，这样形成的序列即为作业的最优加工顺序。

示例代码实现

假设有n个作业，每个作业的在M1和M2上的加工时间分别存储在数组a[]和b[]中。

编号	1	2	3	4
M1	5	12	4	8
M2	6	2	14	7

1. 对作业进行分组 集合

1和3显然在集合A 按M1升序排列 则顺序为 3 1

2和4显然在集合B 按M2降序排列 则顺序为 42

然后按N1 N2顺序执行 也就是3142

计算时间

f1[i]=f1[i-1]+a[best[i]]

f2[i]=max{f1[i-1],f2[i-1]}+v[best[i]]

8、动态规划-基于递归思想dynamic programming

倒着想！ 一定从末尾想到头 然后确定头的边界条件 把从末尾到头部发生的可能的情况列出

8.3最长子序列和 略 n个整数序列 On

边界条件 dp[0]=0

dp[i]=max{dp[i-1]+a[i],a[i]} 1<=i<=n前i个数的最大连续子序列和

忘了就自己出两个数看一看

8.4三角 从上到下挑选一条最短路On²

dp[1][1]=a[1][1]

dp[i][0]第一列

dp[i][i]对角线

dp[i][j]=min{dp[i-1][j-1],dp[i-1][j]}+a[i][j] (非边界)

8.5求解最长公共子序列 LCS怎么得

假设两个序列X （1，2，3，…m）和Y（1，2，3，…,n）

定义二维动态规划数组

dp[i][j] ij为考虑X（1，2，3，…,i）考虑Y(1,2,3,…,j)时候的最长公共子序列的长度

情况1 X[i]=Y[j]

dp[i][j]=dp[i-1][j-1]+1 那么dp就加1（多一种情况）

情况2 X[i]!=Y[j]不同

那么我就从后往前找 两个里面选一个从后退一步 退一个数

dp[i][j]=max{dp[i-1][j] , dp[i][j-1]}，退一步不改变数量

走到头了dp[0][0]=0，因为我要从第1个开始

时间复杂度Omn 两个数组的大小乘积

8.6最长递增子序列LIS 引入j 0<=j<i 解决不是连续的情况

给定数组a[1,2,…,n]

dp[0]=0;

dp[i] = 1 + max(dp[j]) 其中 0 <= j < i 且 a[j] < a[i]

另外最长连续递增子序列

dp[i] = dp[i-1] + 1 如果 a[i] > a[i-1] dp[i] = 1 如果 a[i] <= a[i-1]前面一个数比后面一个大，那么动态规划清1，重新累加，很合理

8.8 0/1背包 时间复杂度 O 空间x数量

例如,如果我们正在解决一个简单的背包问题,我们可以定义状态 dp[i][j]为前 i 个物品,总重量不超过 j 的最大价值.状态转移方程可以写为： dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]) 这个状态转移方程表示,对于前 i 个物品,我们可以选择不放入第 i 个物品,此时总价值为 dp[i-1][j]；或者我们可以选择放入第 i 个物品,此时总价值为 dp[i-1][j-weight[i]] + value[i].我们选择两者中的最大值作为 dp[i][j]的值.

设置二维动态规划数组dp[i][r] i表示考虑前i个物品的情况，r表示背包剩余容量

边界条件

dp[i][0]=0 不剩空间了

dp[0][r]=0 不剩物品了

dp[i][j]= dp[i-1]][r] 放不下物品

dp[i][j]=max{dp[i-1][r-w[i]]+v[i],dp[i-1][r]}; 放得下物品考虑放不放

注意01背包选择了当前的物品后直接返回一层

完全背包选择了当前的物品后还可以继续选，所以不立刻返回

放入,剩余空间缩小，价值增加，不放，空间价值不变，取其中max

最后得到dp[n][r]=所求的最优价值

解向量：需要手动模拟，代码层面直接记录 dp值变了肯定是用了

8.9求解完全背包问题 略

完全背包问题是一种典型的动态规划问题，它与0-1背包问题类似，但区别在于每种物品可以选择无限次。给定n种物品和一个容量为W的背包，物品i的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的总价值最大，同时确保总重量不超过背包的容量。

状态转移方程

定义dp[i][j]为考虑前i种物品，当前背包容量为j时的最大价值。状态转移方程如下：

dp[i][j] = max{dp[i-1][j], dp[i][j-w[i]] + v[i]}

注意选择了物品的情况 没有立刻返回

解释：

• dp[i-1][j]表示不选择当前第i种物品的情况。
• dp[i][j-w[i]] + v[i]表示选择当前第i种物品的情况，由于是完全背包，选择一次后仍可以继续选择，因此是dp[i][...]而不是dp[i-1][...]。

初始化

• dp[0][...] = 0：没有物品时，价值为0。
• dp[...][0] = 0：背包容量为0时，价值为0。

##

8.10n个商店 m个员工 资源分配 略

i表示考虑1~i个商店的情况 1<=i<=n

从后往前跑dp[i][m] = max(dp[i-1][m-j] + profit(i, j)) 对于所有 0 <= j <= m profit(i, j)表示将j个员工分配给第i个商店所获得的盈利

最佳盈利是dp[n][m]

8.11会议安排 略

贪心+动态规划nlogn

dp[i]表示A[0,..i]的订单中所有兼容订单的最长时间

dp[0]=t[0]

dp[i]=max{dp[i-1],dp[j]+t[i]} j表示第i个活动之前结束的最后一个活动的索引

8.12滚动数组不看

重点多看

总结0/1背包

第一种是要求物品质量刚好是W，这种用回溯 左右剪枝基于重量

第二种是要求物品质量不超过W，回溯与分支限界类似

回溯

W为限制总重量，

令

i为操作步骤，No为物品编号，wi为物品i的重量，vi为物品i的价值，vi/wi为物品的单位价值。物品按单位价值从高到低降序排列

左剪枝条件：仅考虑totalWeight+weight[i]≤W的左孩子节点

右剪枝:仅考虑upperBound(i,totalWeight,totalValue)≥maxv的右孩子节点，

其中upperbound为上界价值函数（需要参数为：当前操作步骤数、总重量、总价值），用于贪心求解上界价值，maxv为当前已搜索到的最高价值。然后开始绘制子集树，时间复杂度T(n)=O(2ⁿ)

重点：遍历顺序是严格按照（DFS）

队列式分支限界

队列式分支限界法

重点是遍历顺序严格按照（BFS）

W为限制总重量，

令

i为操作步骤，No为物品编号，wi为物品i的重量，vi为物品i的价值，vi/wi为物品的单位价值。物品按单位价值从高到低降序排列。

初始化

• 队列queue：初始化一个空队列。
• 根节点：创建一个节点，表示没有任何物品被选择的状态，即总重量和总价值都为0。将这个节点加入队列。

BFS过程

对于队列中的每个节点（Node），执行以下操作：

1. 检查终止条件：如果当前节点已经考虑了所有物品（即Node.i == 物品总数），更新最大价值maxv（如果当前节点的价值大于maxv），然后跳过生成子节点的步骤。
2. ** 生成子节点**：
   • Node1（选择当前物品）：如果选择当前考虑的物品i不会使总重量超过W（Node.totalWeight + w[i] ≤ W），则创建一个新节点Node1，表示选择了物品i。更新Node1的总重量和总价值，并将其加入队列。
   • Node2（不选择当前物品）：无论当前的总重量是多少，都创建一个新节点Node2，表示不选择物品i。Node2的总重量和总价值与当前节点相同，并将其加入队列。
3. 剪枝：
   • 左剪枝：如果Node1的总重量超过W，不将Node1加入队列。
   • 右剪枝：对于Node2，计算其上界价值upperBound。如果upperBound < maxv，则不将Node2加入队列。上界价值可以通过贪心算法计算，即在不超过重量限制的情况下，尽可能选择单位价值最高的物品。
4. 更新最大价值：在每次从队列中取出节点时，如果该节点的价值大于当前的maxv，则更新maxv。

结束条件

当队列为空时，搜索结束。此时的maxv即为0/1背包问题的最优解。

时间复杂度分析

• 理论最坏情况：O(2^n)，n为物品数量。每个物品都有选择或不选择两种可能。
• 实际情况：由于剪枝的效果，实际的时间复杂度通常远低于O(2^n)。

初始化一个队列queue，首先将根节点（没有任何物品被选择，总重量和总价值都为0）加入队列。

对于队列中的每个Node，进行如下操作：

1. 生成子节点：对于节点Node，生成两个子节点Node1和Node2。Node1代表选择当前考虑的物品i（如果加入该物品后总重量不超过W），Node2代表不选择当前考虑的物品i。
   • 左剪枝条件：对于左孩子(Node1)，仅当Node1.totalWeight + w[Node1.i] ≤ W时，才考虑这个左孩子节点，否则进行剪枝。
   • 右剪枝条件：对于右孩子(Node2），仅当Node2.upperBound≥ maxv时，考虑这个右孩子节点。其中upperBound为上界价值函数，用于贪心求解上界价值；maxv为当前已搜索到的最高价值。

最终，maxv即为0/1背包问题的解。

时间复杂度T(n)主要取决于队列中节点的数量，理论上最坏情况下与回溯法相同，为O(2ⁿ)，但实际上由于剪枝的效果，通常会显著低于O(2ⁿ)。

---

优先队列式分支限界

重点是出队顺序和遍历顺序是基于高价值优先，即优先遍历“要选”，其次是“不选”

W为限制总重量，

1. 令i为操作步骤，No为物品编号，wi为物品i的重量，vi为物品i的价值，vi/wi为物品的单位价值。物品按单位价值从高到低降序排列。
2. 初始化：定义一个优先队列priorityQueue，按照某种策略（如上界价值或当前价值）优先级排序，首先将根节点（没有任何物品被选择，总重量和总价值都为0，步骤i=0）加入优先队列。
3. 循环处理队列中的节点：
   • 从priorityQueue中取出一个节点Node（优先级最高的节点），进行扩展。
   • 对于节点Node，生成两个子节点Node1和Node2。Node1代表选择当前考虑的物品i（如果加入该物品后总重量不超过W），Node2代表不选择当前考虑的物品i。
     • 左剪枝条件：对于Node1，仅当Node1.totalWeight + w[Node1.i] ≤ W时，才考虑这个左孩子节点，否则进行剪枝。
     • 右剪枝条件：对于Node1和Node2，计算upperBound，仅当upperBound ≥ maxv时，考虑这个子节点。upperBound为上界价值函数，用于贪心求解上界价值；maxv为当前已搜索到的最高价值。

时间复杂度：T(n)主要取决于优先队列中节点的数量和处理每个节点的时间。由于使用了优先队列和剪枝策略，虽然理论上最坏情况仍然是O(2ⁿ)，但实际运行时间通常会显著低于回溯法和简单的队列式分支限界法。

时间复杂度汇总

1. 分治：有序数列折半查找（二分查找 计算中点） logn 砍掉一半 只分不合
2. 分治：两个等长有序序列中位数 logn 一半一半地砍掉 只分不合
3. 分治：寻找第k小 n 双指针算法 确定基准，移动大于、小于基准地元素到同侧，计算小于基准的元素个数 边调整位置边比较 平均来看是n 最坏n²
4. 分治：一个无序列表查找最大和次大 n 时间复杂度分析：
   • 对于 n 个元素，分治法在每一层递归中大约需要 n/2 次比较来找到最大元素（因为每次比较都是成对出现的）。
   • 对于次大元素的查找，由于次大元素是在最大元素的“对手”中选出的，这个过程的比较次数不会超过最大元素在其胜利路径上的比较次数，大约是 logn 次（因为每一层递归最大元素都需要比较一次）。
   • 因此，总的比较次数大约是 n + logn，这仍然是 O(n) 的时间复杂度。
   为什么不是O(nlogn)？尽管分治法听起来像是每次都将问题规模减半，似乎应该导致 O(nlogn) 的时间复杂度，但实际上，由于在合并步骤中并没有对所有元素进行全面的比较，而是只在有限的“对手”中选择次大元素，因此避免了额外的比较开销，使得总体时间复杂度保持在 O(n)。这与排序不同，排序需要在每一层递归中对元素进行更全面的比较和排列，导致了 O(nlogn) 的时间复杂度。
5. 分治：二路归并 无论自顶向下或是自底向上 nlogn —-排序 分logn了又合n
6. 分治：最大连续子序列和（分治）nlogn 折半分 左侧 右侧 中间 取三者最大 分了又合
7. 蛮力：连续子序列 n³ 可优化到 n² 三重循环的过程：一重设置起点 二重设置重点 三重 计算从起点到重点得到的子序列和 优化是把第三步融入到第二步
8. 蛮力：幂集 n*2ⁿ 指数级 先构造0~2ⁿ-1大小的空间存放每个整数 每个整数代表一个子集（二进制表示）遍历每个数需要n 合并在一起就是幂集
9. 蛮力：全排列 n*(n!) 插空法 把新的元素插入上一步生成的空隙中 指数级

上下界剪枝函数理解

例如0/1背包 仅考虑上界upperBound≥maxValue的情况

上界函数计算过程是：按单位价值排好序后，从上到下能装就装，遇到装不到的就用乘法去乘权重（虽然不合题目要求，但是是上界，辅助剪枝）

类似的 队列式/优先队列式剪枝 任务分配/流水线 要求最短时间

设置下界函数lowerBound

仅考虑lowerBound≤minCost的情况

例如任务分配，把i号人依次分配到1，2，3，4号任务上，分配的是人，那么lowerBound=确定的时间+每个人不管(限制)选取最适合自己的方案所产生的时间

对于实际问题，剪枝设置方法不同

比较问题？

分治法、蛮力法、回溯法、分支限界法、贪心法和动态规划是解决问题的常见算法策略，它们在解决问题的方式、效率、适用场景等方面有着显著的不同。以下是这些策略之间值得比较的几个关键方面：

1. 基本思想：
   • 分治法：将原问题分解为若干个规模较小但类似于原问题的子问题，递归解决这些子问题，然后合并这些子问题的解以得到原问题的解。
   • 蛮力法（暴力法）：尝试问题的所有可能状态，直到找到问题的解。
   • 回溯法：通过试错来找到问题的解，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答时，它将取消上一步甚至是上几步的计算，再通过其他可能的分步解答再次尝试寻找问题的解。
   • 分支限界法：类似于回溯法，但是采用广度优先或最小成本优先策略，通过维护一个全局变量（如最小成本）来避免无望的路径。
   • 贪心法：在对问题求解时，总是做出在当前看来是最好的选择，不从整体最优解考虑，只求局部最优解。
   • 动态规划：将复杂问题分解成小问题进行解决，小问题的解会被保存以便以后重用，以达到减少计算量的目的。
2. 效率：
   • 蛮力法往往效率最低，因为它尝试所有可能的解。
   • 分治法和动态规划通常效率较高，因为它们减少了不必要的计算。
   • 回溯法和分支限界法的效率介于两者之间，取决于剪枝的效果。
   • 贪心法通常运行速度最快，但不总是能得到全局最优解。
3. 适用场景：
   • 分治法适用于问题可以被分解为独立子问题的情况。
   • 蛮力法适用于问题规模较小，或者没有更好的算法时。
   • 回溯法适用于需要遍历所有可能状态的问题，如排列、组合、子集问题。
   • 分支限界法适用于求解优化问题，特别是在状态空间树的搜索中。
   • 贪心法适用于问题的局部最优解能决定全局最优解的情况。
   • 动态规划适用于有重叠子问题和最优子结构性质的问题。
4. 是否保证最优解：
   • 蛮力法、分治法、回溯法、分支限界法和动态规划通常能保证找到最优解。
   • 贪心法不总是能保证找到全局最优解，但在某些问题上能提供一个足够好的解。

背包问题

携带重量刚好为W

携带重量不超过W

0/1背包

每个物品只能选或不选

完全背包

每个物品可以选择无限次

多重背包

每个物品可以选择有限次

分数背包

每个物品可以选择一部分

用贪心策略，每次选择单位重量价值最大的物品即可，很好理解

同样的反证法，

假设存在唯一最优解S’，且其解空间中存在物品没有按单位重量价值递减的顺序被消耗的情况，则始终可以用部分同质量的单位价值高的未被使用的物品，去替换部分同质量的单位重量价值低的物品，得到的S”一定优于S’,这便产生矛盾.进一步，由于贪心选择的解S在每一步都是局部最优的，且比任何其他解更优，因此S也是全局最优解。

应用

任务分配,n*n矩阵内n个人,n项任务

活动安排 不冲突求最多活动

贪心nlogn

流水线 M1 M2

f1[i]=f1[i-1]+M1[i]

f2[i]=max{f1[i-1],f2[i-1]}+M2[i]

贪心nlogn

多机调度 n台机 大于n个任务 求最短时间