目录
8-1 计算题-时间复杂度分析
8-2 动态规划法与贪心法的异同
8-3 矩阵连乘
8-4 最大子数组和
8-5 旅行商问题
8-6 算法设计题-0-1背包问题
8-7 算法设计题-活动安排
8-8 算法设计题-找零钱问题
以下答案仅代表个人想法，仅供参考
8-1 计算题-时间复杂度分析
已知一个分治算法耗费的计算时间T(n)，T(n)满足如下递归方程：
请求解此递归方程。(logn为
的简记)
解：
8-2 动态规划法与贪心法的异同
简述动态规划法与贪心法的异同。
解：
同：
贪心法和动态规划算法都要求问题具有最优子结构性质
异：
动态规划：依赖于子问题的解，自底向上或自顶向下求解
贪心法：不依赖于子问题的解，自顶向下求解
动态规划的条件：子问题的重叠性质
贪心法的条件：最优子结构性质，贪心选择性质
8-3 矩阵连乘
利用动态规划法计算矩阵连乘积A1A2A3A4A5的最佳求积顺序（即：数乘次数最少的计算次序），各矩阵的维数分别为：
（要求给出计算步骤）
解：
递推式m[i][j]=m[i][k]+m[k+1][j]+pi-1*pk*pj
m数组为第i个矩阵到第j个矩阵的最小乘法执行次数
s为断开位置即为每个式子里的k
计算顺序(((A1A2)(A3A4))A5)
执行乘法次数为1655
8-4 最大子数组和
已知由8个整数构成的序列：（12,-4,7,-5,16,-4,8,7）。
（1）请用分治法求最大子数组和（请给出分解与合并的具体步骤及子数组和）；
（2）请用动态规划法求最大子数组和（请给出递推式、计算过程及最后的子数组及子数组和）；
（3）请根据该题，对比分治法与动态规划法的异同（请给出不少于4个异同点）。
解：
（1）
分解步骤：
1、将序列分为两半：左区间部分为（12, -4, 7, -5），右区间部分为（16, -4, 8, 7）。
2、递归地求左区间和右区间的最大子数组和。
3、求跨越两半部分的最大子数组和。
合并步骤：
1、左区间的最大子数组和
分解为（12, -4）和（7, -5）
（12, -4）的最大子数组和为12
（7, -5）的最大子数组和为7
跨越（12, -4）和（7, -5）的最大子数组和为12 + (-4) + 7 = 15
左半部分的最大子数组和为15
2、右区间的最大子数组和
分解为（16, -4）和（8, 7）
（16, -4）的最大子数组和为16
（8, 7）的最大子数组和为15
跨越（16, -4）和（8, 7）的最大子数组和为16 + (-4) + 8 + 7 = 27
右半部分的最大子数组和为27
3、跨越两个区间的最大子数组和：
从左区间的末尾开始向左求最大子数组和：12 + (-4) + 7 + (-5) = 10
从右区间的开始向右求最大子数组和：16 + (-4) + 8 + 7 = 27
跨越两半部分的最大子数组和为10 + 27 = 37
最大子数组和为37，最大子数组为（12,-4,7,-5,16,-4,8,7）
（2）
设dp[i]表示前i个元素中的最大子数组和
递推式为
dp[0]=0
dp[i]=max(dp[i-1]+a[i],a[i])
计算过程
初始化dp[0]=0
计算dp[1] = max(dp[0] + 12, 12) = 12
计算dp[2] = max(dp[1] + (-4), -4) = 8
计算dp[3] = max(dp[2] + 7, 7) = 15
计算dp[4] = max(dp[3] + (-5), -5) = 10
计算dp[5] = max(dp[4] + 16, 16) = 26
计算dp[6] = max(dp[5] + (-4), -4) = 22
计算dp[7] = max(dp[6] + 8, 8) = 30
计算dp[8] = max(dp[7] + 7, 7) = 37
最大子数组和为37，最大子数组为（12,-4,7,-5,16,-4,8,7）
（3）
两者的共同点是将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
两者的不同点如下：
适合用动态规划法求解的问题，分解得到的各子问题往往不是相互独立的(重叠子问题性质)，而分治法中的子问题相互独立；
另外，动态规划法用表保存已求解过的子问题的解，再次碰到同样的子问题时不必重新求解，只需查询答案，故可获得多项式级时间复杂度，效率较高，而分治法中对于每次出现的子问题均求解，导致同样的子问题被反复求解，故产生指数增长的时间复杂度，效率较低。
8-5 旅行商问题
用分支限界法求解旅行商问题，如图所示，n=4，城市1为售货员所在的城市，请画出最终的搜索树。
解：
旅行商问题要求，从某一点开始行走，经过其他所有的点，并回到初始点的最短路径
路径上的数字为下一个走到的城市，结点上的数字为当前走过的城市所需走的距离之和
如图
搜索所有路径情况
1，2，3，4，1 距离为59
1，2，4，3，1 距离为66
1，3，2，4，1 距离为25
1，3，4，2，1 距离为66
1，4，2，3，1 距离为25
1，4，3，2，1 距离为59
最短路径为
1，3，2，4，1 距离为25
1，4，2，3，1 距离为25
8-6 算法设计题-0-1背包问题
（提示：算法设计题，要先用文字阐述算法设计思想，然后用伪代码的形式给出算法，最后要进行算法时间复杂度分析，另如果用到贪心算法，则需要分析其是否具体贪心选择性质）
0-1背包问题∶给定n种物品和一背包，物品i的重量是wi，其价值为vi，背包的容量为C.问应该如何装入背包，使得背包中物品的总价值最大？写出用回溯法解决该问题的算法。
解：
对于01背包问题使用回溯算法，每个物品有选和不选两个状态，递归搜索所有可能的情况进行搭配
定义数组 v[1...n], w[1...n], st[1...n] 定义整数 n, m, res 初始化为 0 定义整数 sum 初始化为 0函数 dfs(x)如果 x == n + 1返回结束如果对于 i 从 1 到 n如果 st[i] == 0 且 m - v[i] >= 0设置 st[i] = 1m = m - v[i]sum = sum + w[i]res = max(sum, res)调用 dfs(x + 1)设置 st[i] = 0m = m + v[i]sum = sum - w[i]结束如果结束对于 结束函数主程序输入 n 和 m对于 i 从 1 到 n输入 v[i] 和 w[i]结束对于调用 dfs(0)输出 res 结束主程序总共有n个物品，每个物品有选和不选两个状态，所以时间复杂度为O(n2^n)
8-7 算法设计题-活动安排
（提示：算法设计题，要先用文字阐述算法设计思想，然后用伪代码的形式给出算法，最后要进行算法时间复杂度分析，另如果用到贪心算法，则需要分析其是否具体贪心选择性质）
某体育馆有一羽毛球场出租，现在总共有10位客户申请租用此羽毛球场，每个客户所租用的开始时间和结束时间如下表所示，其中s(i)表示开始租用时间，f(i)表示结束租用时间：
同一时刻，该羽毛球场只能租给一位客户，请设计一个租用安排方案，在这10位客户里面，使得体育馆尽可能满足多位客户的需求，并算出针对上表的10个客户申请，最多可以安排几位客户申请？
解：
本题使用贪心算法，由于一次只能租给一位客户，所以需要尽早开始尽早使租用时间结束，我们需要按结束时间从小到大排序，排序后如下
排序后如下：
伪代码：
首先记录开始时间和结束时间在q数组中，q数组的数据类型为包含两个int类型的结构体
开始// 输入元素个数 n输入 n// 初始化结构体数组 q，用于存储每对开始时间和结束时间对于 i = 1 到 n输入 q[i].a 和 q[i].b结束// 使用快速排序进行排序对 q[1] 到 q[n] 进行排序// 初始化变量sum = 0dq = 0// 遍历排序后的数组 q对于 i = 1 到 n如果 i = 1dq = q[i].bsum = sum + 1否则如果 q[i].a >= dqdq = q[i].bsum = sum + 1结束如果结束//输出最多能安排的客户输出 sum 结束由于存在排序，使用快速排序的平均时间复杂度为O(nlogn)，检查客户所用的时间复杂度为O(n)，所以该算法的时间复杂度为O(nlogn)
按照上述策略，我们选择了以下客户：3, 6, 7, 9，所以最多可以安排4位客户的申请。
8-8 算法设计题-找零钱问题
（提示：算法设计题，要先用文字阐述算法设计思想，然后用伪代码的形式给出算法，最后要进行算法时间复杂度分析，另如果用到贪心算法，则需要分析其是否具体贪心选择性质）
小明是一个销售员，客人在他的地方买了东西，付给了小明一定面值的钱之后，小明需要把多余的钱退给客人，客人付给了小明n，小明的东西的售价为m，小明能退回给客人的面额只能为[100,50,20,10,5,2,1]的组合，设计一种策略，使小明想要使找出去纸币张数最小。（不需要写出详细代码，只需写出使用的算法策略名称、算法策略、数据准备以及程序实现流程）
解：
算法策略由于需要找出去的纸币张数最小，所以需要优先找给客人大面额的纸币
数据准备
客人付的金额n
小明商品的售价m
可以退回顾客的面额用数组sz存[100,50,20,10,5,2,1]
程序实现流程：
首先计算出需要找的金额数，面额数组已经从大到小排序好，如果没排序好需要排序，所以只需遍历一遍面额数组即可，优先取出面额大的纸币找钱
时间复杂度分析：
由于面额数组已经从大到小排序好，只需遍历一遍面额数组即可，所需的时间复杂度为O(n)，其中n为面额数组的长度
伪代码：
cnt=0 //记录需要找回的纸币数 change=n-m //需要找回的金额 对于 i=1 到sz数组长度如果 change >= sz[i]:change-=sz[i]cnt+=1如果 change == 0:break 输出cnt
