盐城做企业网站多少钱,企业网站 自适应,网红营销成功案例,网站建设与管理课程标准文章目录 第一章 概述算法与程序时间复杂性求上界 第二章 递归与分治双递归函数——Ackerman函数分治策略大整数乘法两位两位四位x四位 三位x三位两位x六位 第三章 动态规划矩阵连乘基本要素最优子结构子问题重叠 备忘录 第四章 贪心算法活动安排问题基本要素贪心选择性质最优子… 文章目录 第一章 概述算法与程序时间复杂性求上界 第二章 递归与分治双递归函数——Ackerman函数分治策略大整数乘法两位×两位四位x四位 三位x三位两位x六位 第三章 动态规划矩阵连乘基本要素最优子结构子问题重叠 备忘录 第四章 贪心算法活动安排问题基本要素贪心选择性质最优子结构性质与动态规划的区别 背包问题物体可分物体不可分 第五章 回溯法**问题的解空间**0-1背包迭代回溯0-1背包问题树结构 期末考点 第一章 概述
算法与程序 算法解决问题的一种方式或者一种过程。算法有若干个指令组成的有穷序列。 程序算法用某种程序设计语言的具体实现 算法的4种性质
输入输出确定性有限性 程序可以不满足“有限性” 时间复杂性
算法复杂度的高低体现在运行该算法所需要的计算机资源的多少上。资源的多少依赖于要解决问题的规模(N)、算法的输入(I)和算法本身的函数(A)
关于时间复杂性分为三种情况最坏情况、最好情况和平均情况。 可操作性最好且最有实际价值的是最坏情况的时间复杂度。
求上界
当NN0时有f(N)Cg(N),称为函数f(N)的一个上界是Cg(N)记作f(N)O(g(N)) 这个上界的阶越低则评估越精确结果越有价值
如何求上界 1.把f(N)函数中的所有阶放大到最高阶合并后并记为Cg(N) 2.此时f(N)Cg(N)把这两个函数去化简即可得条件即n值。 例子f(n)3n210n 最高阶是n2所有阶放大到最高阶得3n210n213n2,记为Cg(N) 此时C13g(N)n2 当3n210n 3n210n2时即10n 10n2时条件成立。 故n01 综上当n01时,C13f(n)O(n2) 注意放大方向不变方式可以改变即可以增大阶层且缩小系数如3n210n 3n2n2,此时结果的C和n0都不一样但f(n)始终一样。 第二章 递归与分治
递归代码效率好但是空间效率和时间效率差
如何改进 消除递归有两种方式:阶乘循环和阶加循环、通项公式
双递归函数——Ackerman函数
定义一个函数及它的一个变量由函数自身定义时
分治策略
基本思想将问题分解为k个小规模的子问题这些子问题相互独立且原问题相同。递归地解这些子问题将个子问题的解合并得到原问题的解。
大整数乘法
普通乘法的时间复杂度是O(n2) 通过分支策略可达到O(n1.59)
两位×两位
步骤 1.两位数分出高低位 2.套用公式求p,q,r 遇到负数高低位都带符号 如-23高位-2低位-2。至此-23(-2)*10(-3) 最简的分治递归出口一位x一位
四位x四位
一直递归直到满足出口
三位x三位
往前补0公式不变
两位x六位
补零或者把六位拆成3个两位
第三章 动态规划
动态规划分治同分解子问题分解子问题异子问题相互依赖子问题相互独立
基本思想 分解成子问题求解时有些子问题被重复计算许多次。用一个表来记录所有已解决的子问题的答案而在需要时再找出已求得的答案就可以避免大量的重复计算。
步骤 1.找到最优解刻画其结构性质 2.递归地定义最优值 3.以自底向上的方式计算最优值 4.根据计算最优值时得到的信息构造最优解
矩阵连乘
题目背景 若两矩阵相乘需满足第一矩阵的行第二矩阵的列 即Amxn X Bpxq的条件为np 此时乘法次数为m x n x q 连乘次序会影响乘法次数 按照上述步骤 1.最优解及其结构性质最小乘法次数 及 最小乘法次数的断开处 记A[i:j]是AiAi1…Aj 问题A[1:n]可以在k1,2,⋯n−1处断开若A[1n]最优则A[1k]与A[k1:n]也最优
2.建立递归关系 记A[i:j]其中1≤i≤j≤n最少乘法次数记m[i][j] (1)当ij时→ A[i:i] →指A[i] 本身→乘法次数为0,即 m[i][j]0 (2)当ij时 在k处断开 k可以取值i, i1, ∙∙∙, j−1在某k处乘法次数最少 定义数组p存储矩阵信息 p[0]为第1矩阵的行 p[1]为第1矩阵列也为第2矩阵行 p[2]为第2矩阵列也为第3矩阵行 p[3]为第3矩阵列也为第4矩阵行 … p[n]为第n矩阵列
3.计算最优值 对于结果的存储使用m表存储最小乘法次数即最优值用s表存储k值即最优解
代码实现
//构造最优值
void MatrixChain(int *p, int n, int **m, int **s)//P一维数组记下标n矩阵个数m表s记分段
{for(int i1;in;i)m[i][i]0;//对角线上都填0for(int r2;rn;r)//在m表中从第2条填到第n条(对角线)for(int i1;in-r1;i)//i是行下标从第1行开始填一个倒三角的表{int jir-1;//列下标m[i][j]0m[i1][j]p[i-1]*p[i]*p[j];//实现递归计算先初始化第1项省略了m[i][i]s[i][j]i;//s记分段点此为s的初值for(int ki1;kj;k)//递归式从ki1到j-1找最小{int tm[i][k]m[k1][j]p[i-1]*p[k]*p[j];//递归式计算 if(tm[i][j]){m[i][j]t;//记入最小值s[i][j]k;//记入划分位置}}}
}
4.构造最优解 算法MatrixChain只是计算出了最优值并未给出最优解。但是MatrixChain已记录了构造最优解所需要的全部信息。s[i][j]中的数表明最佳方式应在矩阵的何处断开。
//构造最优解
void Traceback(int i,int j,int **s)//求A[i:j]的最优解构造利用s[][]设已知s[i][j]k
{if(ij)return ;//A[i:i]不必构造递归出口Traceback(i,s[i][j],s);//求A[i:k]的构造记1Traceback(s[i][j]1,j,s);//求A[k1:j]的构造记2coutMultiply A[i:s[i][j]]and A[(s[i][j]1):j]endl;//输出Ai,k And Ak1,j表明在k处断开记3
}基本要素
最优子结构
设计动态规划算法的第一步通常是要刻画最优解的结构。 当问题的最优解包含了其子问题的最优解时称该问题具有最优子结构性质。
子问题重叠
在用递归算法自顶向下解此问题时每次产生的子问题并不总是新问题有些子问题被反复计算多次。 动态规划算法正是利用了这种子问题的重叠性质对每一个子问题只解一次而后将其解保存在一个表格中当再次需要解此子问题时只是简单地用常数时间查看一下结果。
备忘录
动态规划的变形——备忘录 动态规划保存所有子问题的解 变形动态规划是自底向上备忘录是自顶向下 第四章 贪心算法
工作量贪心算法 动态规划 但是贪心算法的结果可能不是最优结果因为贪心算法并不是从整体最优上加以考虑它所做出的选择只是某种意义上的局部最优选择
所以贪心算法的关键是贪心策略的选择。
活动安排问题
该问题要求高效地安排一系列争用某一个公共资源的活动。有n个活动开始和结束的时间si≤fi如何安排最多个活动
贪心策略按结束时间递增排序从前向后能安排则安排
例题当前有4个活动。
i1234s[i]1305f[i]4567
若选择最早结束优先能使选入活动最多 若最早开始优先仅能安排这一个活动 若最短占用优先则能安排这一个活动
推广 假设要在足够多的的会场里安排一批活动即每个活动都要被安排并希望使用尽可能少的会场。 1贪心策略思路1先在第1会场安排最多活动其次在第2会场安排最多……依此类推 。 2贪心策略思路2视为区间重叠问题。时间点起点和终点。 按时间点排序起点分配1个会场终点回收保证此会场可重复利用
基本要素
贪心选择性质
贪心选择性质是指所求问题的整体最优解是可以通过局部最优的选择即贪心选择达到的。 在动态规划算法中每步所做的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后才能做出选择。 而在贪心算法中仅在当前状态下做出最好选择即局部最优选择。然后再去解做出这个选择后产生的相应子问题。
最优子结构性质
最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。
与动态规划的区别
**贪心算法**先依据贪心策略选择并解一个子问题再进行下一步。 **动态规划算法**先解决所有的子问题比较得出一个最优子问题再进行下一步。
背包问题
问题描述容量为c的背包有n种物品每种物品重w_i价值为v_i其中1≤i≤n 物品不可可以分开。 问如何装入使价值最大
cnw1w2w3v1v2v350310203060100120
物体可分
c0wi0vi01≤i≤n。找x1x2⋯xn0≤xi≤1可为分数即仅取一部分 使 ∑ i 1 n w i ∗ x i c \sum_{i1}^{n} wi*xi c i1∑nwi∗xic 达到最大 ∑ i 1 n v i ∗ x i \sum_{i1}^{n} vi*xi i1∑nvi∗xi
//物品可分贪心算法
#include iostream
#include iomanip
using namespace std;void Knapsack(int n, int c, int*v, int *w, double *x);int main()
{ int n3;//物品数量 int c50;//背包容量 int *vnew int[n1];//价值 int *wnew int[n1];//重量 int i;double *xnew double[n1]; for(i1;in;i)x[i]0; //将数据按贪心策略排序 v[1]60;v[2]100;v[3]120;w[1]10;w[2]20;w[3]30;Knapsack(n,c,v,w,x); for(i1;in;i){ if(x[i]0)cout物品i装入setiosflags(ios::fixed)setprecision(2)x[i]endl;elsecout物品i不装入endl;}return 0;
}void Knapsack(int n, int c, int*v, int *w, double *x)
{int i;for(i1;in;i){if(w[i]c)break;else{x[i]1;cc-w[i]; } } if(in) x[i](double)c/w[i];
}step1准备 按单位价格递减排序x[ ]初值为0先都没选 step2循环 按递减装入物品至不可装为止从1检查到n 物品装入置x[i]1cc−w[i] step3最后 将当前i物品分开送入c/w[i]
物体不可分
其中c0wi0vi01≤i≤n 找x1x2⋯xnxi∈{0,1} 物品没装xi0装入xi1 使 ∑ i 1 n w i ∗ x i c \sum_{i1}^{n} wi*xi c i1∑nwi∗xic 达到最大 ∑ i 1 n v i ∗ x i \sum_{i1}^{n} vi*xi i1∑nvi∗xi
根据上述步骤 1.最优子结构性质 若(y_1y_2⋯y_n)是最优解则(y_2⋯y_n)是子问题的最优解
2.递归关系 m(i,j)记背包容量j可选物品为ii1⋯n时0-1背包问题的最优解 3.计算最优值
template class Type
void Knapsack(Type *v, int *w, int n, Type **m)
{int jMaxmin(w[n]-1,c);//找w[n]的临界值,并避免物品n比背包容量还要大的情况 //最小子问题填写最后一行m[n][j] for(int j0;jjMax;j)m[n][j]0;for(int jw[n];jc;j)m[n][j]v[n];for(int in-1;i1;i--){jMaxmin(w[i]-1,c);for(int j0;jjMax;j)m[i][j]m[i1][j];//物品i装不进去for(int jw[i];jc;j)m[i][j]max(m[i1][j],m[i1][j-w[i]]v[i]);//能装但不装装进去两个值中取较大值 }//填最后一行 m[1][c]m[2][c];//若物品1装不进去 if(cw[1])//若物品1可以装 m[1][c]max(m[2][c],m[2][c-w[1]]v[1]);
}step1实现递归出口填矩阵m的第n行(前3行)step2循环实现递归式填矩阵m的第(n−1)行到第2行step3填m[1][c]4.构造最优解
template class Type
void Traceback(Type **m, int *w, int c, int n, int *x)//m表已经填好已知w、c、n输出x[]0不装1装入
{for(int i1;in;i){if(m[i][c]m[i1][c])x[i]0;//相同则不装else{x[i]1;c-w[i];}}x[n](m[n][c])?1:0; }第五章 回溯法
溯法有“通用的解题法”之称。 用它可以系统地搜索一个问题的所有解或任意解 它在问题的解空间树中按深度优先策略从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时先判断该结点是否包含问题的解。如果肯定不包含则跳过对以该点为根的子树的搜索逐层向其祖先结点回溯否则进入该子树继续按深度优先策略搜索。
问题的解空间 用回溯法解问题时应明确定义问题的解空间。
指包含解的“集合”结构常为树或者图。
问题的解空间至少应包含问题的一个最优解。0-1背包
迭代回溯
有两种方案 第一种是保存所有子集 第二种是添加剪枝函数
3个状态左子树、右子树、回溯 在左、右子树添加约束函数、限界函数 两种剪枝函数 约束函数在扩展结点处剪去不满足约束的子树 限界函数剪去得不到最优解的子树。 0-1背包问题树结构
期末考点
1.熟练求出上界的n0,C,g(N) 2.清楚Ackerman函数的代码实现 3.熟练掌握大整数相乘的p,q,r掌握其求解过程 4.清楚大整数乘法的代码实现尤其是递归出口 5.掌握动态规划中0-1背包的代码实现、m表、s表、及其求最优值的解 6.在动态规划中0-1背包的代码中可能会考察代码填空变量的各阶段的值 7.掌握备忘录代码的具体实现 8.回溯法中的旅行售货员内容 及 整本书的定义内容不会考察。 掌握的意思是必考清楚代表可能重点考察 期末在头歌上考有代码填空及代码分析两种题型
