西安市城乡建设档案馆网站,网站设计的方法,怎么做扒代码网站,seo诊断的网络问题《算法分析与设计》笔记总结第一章 算法引论1.1 算法与程序1.2 表达算法的抽象机制1.3 描述算法1.4 算法复杂性分析第二章 递归与分治策略2.1 递归的概念2.2 分治法的基本思想2.3 二分搜索技术2.4 大整数乘法2.5 Strassen矩阵乘法2.7 合并排序2.8 快速排序2.9 线性时间选择2.10…
《算法分析与设计》笔记总结第一章 算法引论1.1 算法与程序1.2 表达算法的抽象机制1.3 描述算法1.4 算法复杂性分析第二章 递归与分治策略2.1 递归的概念2.2 分治法的基本思想2.3 二分搜索技术2.4 大整数乘法2.5 Strassen矩阵乘法2.7 合并排序2.8 快速排序2.9 线性时间选择2.10 最近点对问题第三章 动态规划3.1 矩阵连乘问题3.3 最长公共子序列3.4 凸多边形最优三角剖分3.9 0-1背包问题3.10 最优二叉搜索树第四章 贪心算法4.2 活动安排问题4.3 最优装载问题4.4 哈夫曼编码4.5 单源最短路径4.6 最小生成树第五章 回溯法5.2 装载问题5.6 0-1背包问题第六章 分支限界法6.5 0-1背包问题6.6 装载问题第一章 算法引论
1.1 算法与程序 算法定义解决问题的方法或过程 算法的性质 1输入有零个或多个外部量作为算法的输入2输出算法产生至少一个量作为输出3确定性组成算法的每条指令是清晰的无歧义的4有限性算法中每条指令的执行次数有限执行每条指令的时间也有限有时还会加入通用性或可行性 程序的定义是算法用某种程序设计语言的具体实现。 程序与算法的区别程序可以不满足算法的第四点性质即有限性。例如操作系统是在无限循环中执行的程序。
1.2 表达算法的抽象机制
为了将顶层算法与底层算法隔开使二者在设计时不互相牵制互相影响必须对二者的接口进行抽象。让底层只通过接口为顶层服务顶层也只通过接口调用底层运算。这个接口就是抽象数据类型(ADT)。
1.3 描述算法
有多种方式如自然语言方式表格方式高级程序语言方式等…
1.4 算法复杂性分析
算法分析的目的分析算法占用计算机资源的情况对算法做出比较和评价设计出更好的算法算法的复杂性是算法运行时所需的计算机资源的量需要时间资源的量称为时间复杂性需要空间资源的量称为空间复杂性。CF(N,I,A)用NIA分别表示算法要解的问题的规模算法的输入和算法本身F表示是上诉NIA的确定的三元函数C表示复杂性一般只考虑3种情况下的时间复杂性即最坏情况最好情况平均情况实践表明可操作性最好且最有实际价值的是最坏情况下的时间复杂性。复杂性渐进性态 对于T(N)如果存在~T(N)使得当N→∞时有(T(N)-~T(N))/T(N)→0那么就说/~T(N)是T(N)当N→∞时的渐进性态。 如果存在正的常数C和自然数N0使得当N≥N0时有f(N)≤Cg(N)则称函数f(N)当N充分大时上有界且g(N)是它的一个上界记为f(N)O(g(N))。这时还说f(N)的阶不高于g(N)的阶。对于符号O有如下运算规则 O(f)O(g)O(max(f,g))O(f)O(g)O(fg)O(f)O(g)O(fg)如果g(N)O(f(N)),则O(f)O(g)O(f)O(Cf(N))O(f(N)),其中C是一个正的常数fO(f) 第二章 递归与分治策略
2.1 递归的概念
直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数 递归函数的两个要素边界条件和递归方程 阶乘函数
#includeiostream
using namespace std;int factorial(int n){if(n0) return 1;else{return n*factorial(n-1);}
}Fibonacci数列
#includeiostream
using namespace std;int fibonacci(int n){if(n1) return 1;else return fibonacci(n-1)fibonacci(n-2);
}hanoi塔
def hanoi(n,a,b,c):#将a上的n个圆盘经过c移动到bif(n0):hanoi(n-1,a,c,b)move(a,b)hanoi(n-1,c,b,a)递归算法的优点结构清晰可读性强容易用数学归纳法来证明算法的正确性递归算法的缺点运行效率低无论是耗费的计算时间还是占用的存储空间都比非递归算法多。消除递归的方法 ①采用一个用户定义的栈来模拟系统的递归调用工作栈从而达到将递归算法改为非递归算法的目的②用递推来实现递归函数
2.2 分治法的基本思想 分治法的基本思想将一个规模为n的问题分解为k个规模较小的子问题这些子问题相互独立且与原问题相同。递归地解这些子问题然后将各子问题的解合并得到原问题的解。 分治法的适用条件 ①该问题的规模缩小到一定程度容易解决。②该问题可以分解为若干个规模较小的相同问题。即该问题具有最优子结构性质。③该问题分解出的子问题的解可以合并为该问题的解。④子问题间不包含公共的子问题各子问题相互独立 分治法的步骤 划分解决合并
2.3 二分搜索技术
def binarySearch(a,x):#a是数组,x是要搜索的数asorted(a)#a要求有序从小到大nlen(a)left,right0,n-1while(leftright):middle(leftright)//2if(xa[middle]):return middleelif(xa[middle]):leftmiddle1else:rightmiddle-1#未找到return -1最坏情况下时间复杂度是O(logn)
2.4 大整数乘法
设x和y都是n位的二进制整数现在要计算他们的乘积xy。如果直接相乘需要O(n^2)步而其分治法是将n位二进制整数X和Y都分为2段每段的长为n/2位
X[A][B],Y[C][D],其中XY有n位ABCD均有n/2位
由此可以得到
XA*2^(n/2)B , YC*2^(n/2)DXY(A*2^(n/2)B)(C*2^(n/2)D)A*C*2^n(A*DC*B)*2^(n/2)B*DA*C*2^n((A-B)(D-C)A*CB*D)*2^(n/2)B*D最后一个式子看起来似乎复杂了但是它仅需做3次n/2位整数的乘法6次加减法和2次移位2.5 Strassen矩阵乘法
对于方阵nnA,B,C有CAB,将它们都分块成4个大小相等的子矩阵每个子矩阵都是(n/2)*(n/2)的方阵[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8iLmTMe7-1596025346681)(https://s2.ax1x.com/2019/11/20/MhaKxS.png)]
2.7 合并排序
def merge(arr,left,mid,right):#leftright为需要合并的数组范围#mid为中间下标左边比中值小右边比中值大ileftjmid1#复制一个临时数组auxarr[:]for k in range(left,right1):#如果左指针超过mid即右边还有剩余if(imid):arr[k]aux[j]jj1#如果右指针超过right即左边还有剩余elif(jright):arr[k]aux[i]ii1#如果左边小则左边合并elif(aux[i]aux[j]):arr[k]aux[i]ii1#如果右边小else:arr[k]aux[j]jj1def mergeSort(arr,left,right):#如果已经遍历完if(leftright):return ;#取中值拆成左右两边mid(leftright)//2#对左半边进行归并排序mergeSort(arr,left,mid)#对右半边进行归并排序mergeSort(arr,mid1,right)#合并算法merge(arr,left,mid,right)最坏情况下的时间复杂度为O(nlogn)
2.8 快速排序
步骤分解递归求解合并
def quicksort(arr,low,high):if lowhigh :indexgetindex(arr,low,high)quicksort(arr,low,index-1)quicksort(arr,index1,high)#快速排序算法核心
#作用将小于基准值的数放在其左边大于在右边
def getindex(arr,low,high):#默认第一个数字为标准值temparr[low]#当未遍历完即左右指针未相遇while(lowhigh):#如果右边大于标准值右指针左移while((lowhigh)and(arr[high]temp)):highhigh-1#此时右指针对应值小于标准值将其复制给左指针位置arr[low]arr[high]#当左边小于标准值左指针右移while((lowhigh)and(arr[low]temp)):lowlow1#此时左指针对应值大于标准值将其复制给右指针位置arr[high]arr[low]#将标准值赋值给左右指针相遇的位置arr[low]temp#此时low左边全部小于等于arr[low],low右边全部大于等于arr[low]return low快排平均情况下的时间复杂度是O(nlogn)最坏情况下的时间复杂度是O(n^2)
2.9 线性时间选择
找出一组数中第X大小的数采用了随机划分算法
2.10 最近点对问题
时间复杂度分析O(nlogn) Copyright: Copyright (c) 2019
Author: Justlovesmile
Title: 最近点对问题
#按x坐标排序的点
class Point1:#x,y为坐标id为序号def __init__(self,xx,yy,index):self.xxxself.yyyself.idindex#按y坐标排序的点
class Point2(Point1):#xy为坐标id为该点按x排序时的序号def __init__(self,xx,yy,index):self.xxxself.yyyself.idindex#表示输出的平面点对
class Pair:#ab为点dist为距离def __init__(self, aa, bb,dd):self.aaaself.bbbself.distdd#求平面上任意两点u,v的距离
def dist(u,v):dxu.x-v.xdyu.y-v.yreturn dx*dxdy*dy#归并排序
def merge(S,order,left,mid,right):ileftjmid1auxS[:]#按x排序if(orderx):for k in range(left,right1):if(imid):S[k]aux[j]jj1elif(jright):S[k]aux[i]ii1elif(S[i].xaux[j].x):S[k]aux[i]ii1else:S[k]aux[j]jj1#按y排序elif(ordery):for k in range(left,right1):if(imid):S[k]aux[j]jj1elif(jright):S[k]aux[i]ii1elif(S[i].yaux[j].y):S[k]aux[i]ii1else:S[k]aux[j]jj1#归并排序
def mergeSort(S,x,left,right):if(leftright):return ;mid(leftright)//2mergeSort(S,x,left,mid)mergeSort(S,x,mid1,right)merge(S,x,left,mid,right)#计算最接近点对
def closePair(S,Y,Z,l,r):#两个点if(r-l1):return Pair(S[l],S[r],dist(S[l],S[r]))#三个点if(r-l2):d1dist(S[l],S[l1])d2dist(S[l1],S[r])d3dist(S[l],S[r])if((d1d2)and(d1d3)):return Pair(S[l],S[l1],d1)if(d2d3):return Pair(S[l1],S[r],d2)else:return Pair(S[l],S[r],d3)#多于三个点m(lr)//2flgm1for i in range(l,r1):if(Y[i].idm):Z[g]Y[i] gg1else:Z[f]Y[i]ff1#递归求解best closePair(S,Z,Y,l,m)right closePair(S,Z,Y,m1,r)#选最近的点对if(right.distbest.dist):bestrightmerge(Y,y,l,m,r)kl#距离中线最近的for i in range(l,r1):if(abs(S[m].x-Y[i].x)best.dist):Z[k]Y[i]kk1for i in range(l,k):for j in range(i1,k):if(Z[j].y-Z[i].ybest.dist):dpdist(Z[i],Z[j])if(dpbest.dist):bestPair(S[Z[i].id],S[Z[j].id],dp)#返回最近点对return best#一维点集
def cpair1(S):#先设为正无穷min_dfloat(inf)Ssorted(S)for i in range(1,len(S)):distabs(S[i]-S[i-1])if(distmin_d):pair[]min_ddistpair.append([S[i-1],S[i]])elif(distmin_d):pair.append([S[i-1],S[i]])print(Closest point:)for i in pair:print(i,end )print(\nMin_dist:,min_d)#二维点集
def cpair2(S):Y[]nlen(S)if(n2):return ;#按X坐标排序mergeSort(S,x,0,n-1)#以Point2类型赋值for i in range(n):pPoint2(S[i].x,S[i].y,i)Y.append(p)#按y坐标排序mergeSort(Y,y,0,n-1)ZY[:]return closePair(S,Y,Z,0,n-1)def main():#输入一维还是二维点平面modelinput(Please choose model of 1 or 2:).split()[0]S[]#一维点对if(model 1):pointinput(Please input a group of number in order:\n).split()#如果输入空点对if(len(point)0):raise ValueError(您输入了空点对)#转换类型for i in range(len(point)):S.append(int(point[i]))#输出最近点对cpair1(S)#二维点对elif(model 2):#输入点数nint(input(Please input how many points:\n))if(n0):raise ValueError(您输入了0个点)for i in range(n):wordsfplease input the No.{i1} point (like: x y) in x order:pointinput(words).split()pPoint1(int(point[0]),int(point[1]),i)S.append(p)#找到最近的一对点对bestcpair2(S)print(fThe closest points are ({best.a.x},{best.a.y}) and ({best.b.x},{best.b.y}).)print(fAnd the distance is {best.dist**0.5}.)else:raise ValueError(没有这个选项)if __name__ __main__:#异常处理try:main()except Exception as e:print(您的输入不合法出错信息如下)print(e)第三章 动态规划 动态规划算法与分治法类似其基本思想也是将待求解问题分解成若干个子问题先求解子问题然后从这些子问题的解得到原问题的解但与分治法不同的是适用于动态规划法求解的问题经分解得到的子问题往往不是相互独立的。 动态规划算法的步骤 ①找出最优解的性质并刻画其结构特征②递归地定义最优值③以自底向上的方式计算出最优值④根据计算最优值时得到的信息构造最优解 动态规划算法的两个基本要素最优子结构与重叠子问题 最优子结构性质问题的最优解包含子问题的最优解重叠子问题在用递归算法自顶向下求解问题时每次产生的子问题并不总是新问题有些子问题被反复计算多次无后效性一个问题被划分阶段后阶段I中的状态只能由I1中的状态通过状态转移方程得来与其他状态没有关系特别是与未发生的状态没有关系 动态规划算法有一个变形方法——备忘录方法这种方法不同于动态规划算法“自底向上”的填充方向而是“自顶向下”的递归方向为每一个解过的子问题建立一个记录项备忘录以备需要时查看也可以避免相同子问题的重复求解
3.1 矩阵连乘问题
m(i,j)是指从A[i]到A[j]1≤i≤j≤n的最少数乘次数矩阵可乘条件A的列数等于B的行数若A是一个p×q矩阵B是一个q×r矩阵则AB总共需要pqr次数乘。 Copyright: Copyright (c) 2019
Author: Justlovesmile
Title: 矩阵连乘问题
#计算最优值
def matrixChain(p,m,s):#m[i][j]表示A[i]到A[j]所需的最少数乘次数#s[i][j]表示A[i]到A[j]所需的最少数乘法对应的分隔位置nlen(p)-1for r in range(2,n1):for i in range(1,n-r2):#沿斜线方向递进jri-1m[i][j]m[i1][j]p[i-1]*p[i]*p[j]s[i][j]iki1#寻找i到j间最优分隔kwhile(kj):tm[i][k]m[k1][j]p[i-1]*p[k]*p[j]if(tm[i][j]):m[i][j]ts[i][j]kkk1#根据S递归输出
def traceback(s,i,j):if(ij):print(fA[{i}],end)return ;print((,end)traceback(s,i,s[i][j])traceback(s,s[i][j]1,j)print(),end)def main():p[]y0#输入矩阵个数ninput(Please iuput the number of matrix:).split()#异常处理if(len(n)0):raise ValueError(您输入了空矩阵)nint(n[0])#输入每个矩阵的信息for i in range(n):sinput(fInput No.{i1} Matrix size,eg:5 5\n).split()#判断是否能与前一项相乘if(len(p)1):if(y!int(s[0])):raise ValueError(您输入的矩阵不能相乘)x,yint(s[0]),int(s[1])p.append(x)p.append(y)m[]s[]for i in range(n1):m.append([0]*(n1))s.append([0]*(n1))matrixChain(p,m,s) traceback(s,1,n)print(\nCount times:,m[1][n])if __name__ __main__:#异常处理try:main()except Exception as e:print(您的输入不合法出错信息如下)print(e)3.3 最长公共子序列
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JlOYpUCL-1596025346688)(https://s2.ax1x.com/2019/11/21/MI179S.png)] 建立递归关系[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kk2SnSy8-1596025346693)(https://s2.ax1x.com/2019/11/21/MI399U.png)] Copyright: Copyright (c) 2019
Author: Justlovesmile
Title: 最长公共子序列问题
def IcsLength(x,y,b):mlen(x)nlen(y)#初始化c[]for j in range(m1):c.append([0]*(n1))#逐个比较for i in range(1,m1):for j in range(1,n1):#如果相等那么此时的最长公共长度为去除该位置的最长公共长度1if(x[i-1]y[j-1]):c[i][j]c[i-1][j-1]1#记录c[i][j]的值是第一类子问题的解得到的b[i][j]1#如果对应位置不相等则比较两个序列去掉这个不等值后哪边的最长子序列会更长elif(c[i-1][j]c[i][j-1]):c[i][j]c[i-1][j]b[i][j]2else:c[i][j]c[i][j-1]b[i][j]3return c[m][n]#根据b[i][j]输出最长子序列
def Ics(i,j,x,b):if(i0 or j0):return ;#如果是第一类子问题的解则说明该位置是公共部分if(b[i][j]1):Ics(i-1,j-1,x,b)print(x[i-1],end)#如果是第二类子问题的解则说明此时Zk≠Xmelif(b[i][j]2):Ics(i-1,j,x,b)#Zk≠Ynelse:Ics(i,j-1,x,b)def main():#输入字符串Ainput(Please input No.1 Ics:).split()Binput(Please input No.2 Ics:).split()b[]for i in range(len(A)1):b.append([0]*(len(B)1))print(The longest length:,IcsLength(A,B,b))Ics(len(A),len(B),A,b)if __name____main__:#异常处理try:main()except Exception as e:print(您的输入不会合法出错信息如下)print(e)3.4 凸多边形最优三角剖分
和矩阵连乘相似 Copyright: Copyright (c) 2019
Author: Justlovesmile
Title: 凸多边形最优三角剖分问题from isConvex import isConvex#计算最优值
def minWeightTriangulation(n,t,s,v):#t[i][j]是凸子多边形vi-1,vi,...,vj的最优三角剖分对应的权函数值for r in range(2,n1):for i in range(1,n-r2):jri-1t[i][j]t[i1][j]weight(i-1,i,j,v)s[i][j]iki1#遍历i到j的所有边while(kj):ut[i][k]t[k1][j]weight(i-1,k,j,v)if(ut[i][j]):t[i][j]us[i][j]kkk1#根据s输出划分结果
def traceback(s,i,j):if(ij):print(fB[{i}],end)return ;print((,end)traceback(s,i,s[i][j])traceback(s,s[i][j]1,j)print(),end)#根据距离计算权重
def weight(i,j,k,v):return dist(i,j,v)dist(i,k,v)dist(k,j,v)#计算距离
def dist(i,j,v):return (v[i][0]-v[j][0])**2(v[i][1]-v[j][1])**2def main():v[]#可选择手动输入和使用默认值ansinput(Do you want to use default v[]:(y / n ))if(ansy or ansY):v[[6,1],[13,1],[16,4],[13,7],[6,7],[3,4]]graph-----######-------\n----#--------#------\n---#----------#-----\n------------------\n---#----------#-----\n----#--------#------\n-----######-------\nprint(graph)for i in v:print(f({i[0]},{i[1]}),end )elif(ansn or ansN):nint(input(Please input the number of points:\n))if(n0):raise ValueError(您输入了0)for i in range(n):ainput(fInput X and Y of No.{i1} point:(eg:X Y)\n).split()v.append([int(a[0]),int(a[1])])else:raise ValueError(对不起没有这个选项)#判断是不是图多边形if(not isConvex(v)):raise ValueError(您输入的不是凸多边形请确认是否按顺序输入)t[]s[]nlen(v)#初始化for i in range(n):t.append([0]*(n))s.append([0]*(n))minWeightTriangulation(n-1,t,s,v)traceback(s,0,n-1)if __name____main__:#异常处理try:main()except Exception as e:print(您的输入不合法出错信息如下)print(e)判断是否为凸多边形
#判断是否为凸多边形计算直线表达式
param vertex1: 前一个顶点
param vertex2: 后一个顶点
return (type, param): 返回直线的类别及其描述参数def kb(vertex1, vertex2):x1 vertex1[0]y1 vertex1[1]x2 vertex2[0]y2 vertex2[1]if x1x2:return (0, x1) # 0-垂直直线if y1y2: return (1, y1) # 1-水平直线else:k (y1-y2)/(x1-x2)b y1 - k*x1return (2, k, b) # 2-倾斜直线
判断是否为凸多边形
param vertexes: 构成多边形的所有顶点坐标列表如[[00], [50, 0], [0, 50]]
return convex: 布尔类型为True说明该多边形为凸多边形否则为凹多边形def isConvex(vertexes):# 默认为凸多边形convex True # 多边形至少包含三个顶点l len(vertexes)if l3:raise ValueError(多边形至少包含三个顶点)# 对每两个点组成的直线做判断for i in range(l):pre inex (i1)%l# 得到直线line kb(vertexes[pre], vertexes[nex])# 计算所有点和直线的距离可能为正也可能为负if line[0]0:offset [vertex[0]-vertexes[pre][0] for vertex in vertexes]elif line[0]1:offset [vertex[1]-vertexes[pre][1] for vertex in vertexes]else:k, b line[1], line[2]offset [k*vertex[0]b-vertex[1] for vertex in vertexes]# 计算两两距离的乘积如果出现负数则存在两个点位于直线两侧因此为凹多边形for o in offset:for s in offset:if o*s0:convex Falsebreakif convexFalse:breakif convexFalse:break# 打印判断结果if convexTrue:print(该多边形为凸多边形)else:print(该多边形为凹多边形)return convex3.9 0-1背包问题
其中m(i,j)是指背包容量为j可选择物品为ii1···n时0-1背包问题的最优值 Copyright: Copyright (c) 2019
Author: Justlovesmile
Title: 0-1背包问题--动态规划
#跳跃点法
def knapsack_Pro(n,v,w,C,p,x):#head指向每一阶段跳跃点集合的开始head[0 for i in range(n1)]p[0][0],p[0][1]0,0left,right,pnext,head[1]0,0,1,1for i in range(n):kleftfor j in range(left,right1):if(p[j][0]w[i]C):break yp[j][0]w[i]mp[j][1]v[i]#重量小于此数的跳跃点直接加进来不会被支配while(kright and p[k][0]y):p[pnext][0]p[k][0]p[pnext][1]p[k][1]pnext1k1#两个if判断新产生的点能否加入pif(kright and p[k][0]y):if(mp[k][1]):mp[k][1]k1if(mp[pnext-1][1]):p[pnext][0]yp[pnext][1]mpnext1#取出可以支配的点while(kright and p[k][1]p[pnext-1][1]):k1#上面break后while(kright):p[pnext][0]p[k][0]p[pnext][1]p[k][1]pnext1k1leftright1rightpnext-1head[i1]pnexttraceback_Pro(n,w,v,p,head,x)def traceback_Pro(n,w,v,p,head,x):jp[head[n]-1][0]mp[head[n]-1][1]print(max value:,m,max weight:,j)for i in range(n)[::-1]:for k in range(head[i],head[i1]-1):if(p[k][0]w[i]j and p[k][1]v[i]m):x[i]1jp[k][0]mp[k][1]breakdef knapsack(v,w,C,m):#m[i][j]指背包容量为j可选择物品为ii1...n时的0-1背包问题的最优值nlen(v)-1#只剩一个物品的情况for j in range(C):m[n][j] v[n] if jmin(w[n]-1,C) else 0#普通情况for i in range(1,n)[::-1]:for j in range(C):m[i][j] max(m[i1][j],m[i1][j-w[i]]v[i]) if jw[i]-1 else m[i1][j]#第一件物品if(n0):m[0][C-1]m[1][C-1]if C-1w[0]:m[0][C-1]max(m[0][C-1],m[1][C-1-w[0]]v[0])def traceback(m,w,C,x):cC-1for i in range(len(w)-1):#没选物品i则x[i]0if (m[i][c]m[i1][c]):x[i]0else:x[i]1c - w[i]#对于最后一个物品x[len(w)-1]1 if m[len(w)-1][c]0 else 0#输出格式
def cout(x,v,w):total_v0total_w0print(Choose:)for i in range(len(v)):if x[i]1:print(fNo.{i1} item: value is {v[i]} , weight is {w[i]})total_v v[i]total_w w[i]print(ftotal value: {total_v})print(ftotal weight: {total_w})def main():v[] #物品的价值列表w[] #物品的重量列表#输入物品数量ninput(Please input the number of items:\n)if(n or n0):raise ValueError(您输入了空值或0)else:nint(n)x[0 for i in range(n1)]#选择两种算法课本上的ansinput(Choose Knapsack or Knapsack_Pro?(1 or 2)\n).split()[0]if ans1:m[] #m(i,j)指背包容量为j可选择物品为ii1...n时的0-1背包问题的最优值for i in range(n):iteminput(fplease input No.{i1} items value(v) and weight(w):(eg:v w)\n).split()v.append(int(item[0]))w.append(int(item[1]))Cint(input(Please input the max weight of bag:\n))if(C0):raise ValueError(背包容量不能≤0)for i in range(n):m.append([0]*C)knapsack(v,w,C,m)traceback(m,w,C,x)cout(x,v,w)elif ans2:for i in range(n):iteminput(fplease input No.{i1} items value(v) and weight(w):(eg:v w)\n).split()v.append(float(item[0]))w.append(float(item[1]))#初始化p[[0 for i in range(2)]for j in range(n*n)]Cfloat(input(Please input the max weight of bag:\n))if(C0):raise ValueError(背包容量不能小于等于0)if(n1):if(w[0]C):x[0]1else:x[0]0else:knapsack_Pro(n,v,w,C,p,x)for i in range(n):if(x[i]1):print(choose: value:,v[i],weight:,w[i])else:raise ValueError(f您输入了{ans}没有该选项)if __name____main__:#异常处理try:main()except Exception as e:print(您的输入不合法出错信息如下)print(e)3.10 最优二叉搜索树
二叉搜索树存储于每个结点中的元素x大于其左子树中任一结点所存储的元素小于其右子树中任一结点所存储的元素 第四章 贪心算法 贪心算法总是做出在当前看来最好的选择也就是说贪心算法并不从整体最优考虑它所作出的选择只是在某种意义上的局部最优选择。 使用贪心算法需满足 贪心选择性指所求问题的整体最优解可以通过一系列局部最优的选择即贪心选择来达到最优子结构性质当一个问题的最优解包含其子问题的最优解时称此问题具有最优子结构性质 贪心算法适合的问题有n个输入其解就由这n个输入满足某些事先给定的约束条件的某个子集组成而把满足约束条件的子集称为该问题的可行解。显然可行解一般来说是不唯一的。那些使目标函数取极值的可行解成为最优解。 贪心算法是一种分级处理方法它首先根据题意选取一种度量标准然后按这种度量标准对这n个的输入排序并按序依次输入如果不满足条件则不把此输入加到解当中。 贪心算法设计求解的核心问题选择能产生问题最优解的最优量度标准。 贪心算法正确性的证明 ①证明算法所求的问题具有优化子结构②证明算法所求解的问题具有贪心选择性③算法按照②种的贪心选择性进行局部最优选择
4.2 活动安排问题
为了选择最多的相容活动每次选择fi最小的活动使能够选择更多的活动度量标准按照结束时间的非减序排列如果有序则O(n)如果无序O(nlogn) Copyright: Copyright (c) 2019
Author: Justlovesmile
Title: 活动安排问题
#活动类每个活动包括开始时间和结束时间
class activity():def __init__(self,ss,ff):self.sssself.fffdef greedySelector(arr,a):nlen(arr)-1a[0]Truej0count1#满足开始时间大于上一个活动的结束时间的加入设为True#O(n)for i in range(1,n1):if(arr[i].sarr[j].f):a[i]Truejicount1else:a[i]Falsereturn countdef main():activities[]#输入数据nint(input(please input the number of activities:\n))#异常处理if(n0):raise ValueError(您输入了0)print(Use greedy selector , activities should be ordered by the end_time.)for i in range(n):iteminput(please input the begin-time and end-time:(eg: 3 6)\n).split()if(len(item)!2):raise ValueError(您输入的数据个数不合法)sactivity(float(item[0]),float(item[1])) activities.append(s)#以结束时间非减序排序activitiessorted(activities,keylambda x:x.f)#初始化选择集合aa[False for i in range(n)]countgreedySelector(activities,a)print(Maximum number of activities:,count)print(Choose:,a)if __name__ __main__:try:main()except Exception as e:print(您的输入不合法出错信息如下)print(e)4.3 最优装载问题
O(nlogn)
4.4 哈夫曼编码
循环地选择具有最低频率的两个结点生成一棵子树直至形成树
#构建二叉树类型
class BinaryTree:def __init__(self,data,left,right,code):self.datadataself.leftleftself.rightrightself.codecodedef getdata(self):return self.data#哈夫曼树
class Huffman:def __init__(self,tree,ww):self.treetreeself.wwwdef getweight(self):return self.wdef huffmanTree(f):#f是出现频率权值字典H[]nlen(f)#根据value对键进行从大到小排序for i in sorted(f,keyf.__getitem__,reverseTrue):tree BinaryTree(i,0,0,)w Huffman(tree,f[i])H.append(w)for i in range(1,n):#取出最后两位xH.pop()yH.pop()#取权重小的做左孩子大的是右孩子tBinaryTree(i,x.tree if x.wy.w else y.tree,y.tree if y.wx.w else x.tree,)hHuffman(t,x.wy.w)H.append(h)#根据权重从大到小排序Hsorted(H,keylambda x:x.w,reverseTrue)return H.pop()Copyright: Copyright (c) 2019
Author: Justlovesmile
Title: 哈夫曼编码
#构建二叉树类型
class BinaryTree:def __init__(self,data,left,right,code):self.datadataself.leftleftself.rightrightself.codecodedef getdata(self):return self.data#哈夫曼树
class Huffman:def __init__(self,tree,ww):self.treetreeself.wwwdef getweight(self):return self.w#计算权重
def makedict(s):dic{}for i in s:if i not in dic.keys():dic[i]1else:dic[i]1return dicdef huffmanTree(f):#f是出现频率权值字典H[]nlen(f)#根据value对键进行从大到小排序for i in sorted(f,keyf.__getitem__,reverseTrue):tree BinaryTree(i,0,0,)w Huffman(tree,f[i])H.append(w)for i in range(1,n):#取出最后两位xH.pop()yH.pop()#取权重小的做左孩子大的是右孩子tBinaryTree(i,x.tree if x.wy.w else y.tree,y.tree if y.wx.w else x.tree,)hHuffman(t,x.wy.w)H.append(h)#根据权重从大到小排序Hsorted(H,keylambda x:x.w,reverseTrue)return H.pop()def listall(h):m[]k[]left,righth.tree.left,h.tree.rightrcode1lcode0m.append(right)right.codercodem.append(left)left.codelcodewhile(len(m)0):#如果存在左孩子左右必同时存在if(m[-1].left):am.pop()ca.codem.append(a.right)a.right.codecrcodem.append(a.left)a.left.codeclcodeelse:bm.pop()k.append(b)return kdef back(hfmcode,filename):ansinput(fDo you want to decode {filename}?y/n\n)if(ans!y and ans!Y):return;#读取要解压缩的文件with open(filename,r) as f:sf.read()st#键和值交换形成新字典new_dict {v:k for k,v in hfmcode.items()}#写入新文件with open(解压缩.txt,w) as f:for i in s:stiif(st in hfmcode.values()):f.write(new_dict[st])stprint(*10)print(ok!Please check the file: 解压缩.txt)print(*10)def main():filename1测试用例.txtfilename2编码后.txt#可以选择读文件和输入字符串sinput(fDo you want to search {filename1}y/n\n)if(sy or sY):#读文件with open(filename1,r) as f:sf.read()#权值字典dicmakedict(s)print(权值,dic)#构建哈夫曼树hTreehuffmanTree(dic)#编码klistall(hTree)print(哈夫曼编码)for i in k:print(i.data,i.code)#存储值对应的编码hfmcode{}for i in k:hfmcode[i.data]i.code#写入哈夫曼编码with open(filename2,w) as f:for i in s:stringhfmcode[i]f.write(string)print(*10)print(fok!Please check the file: {filename2})print(*10)back(hfmcode,filename2)else:sinput(Please input the string:)dicmakedict(s)print(dic)hTreehuffmanTree(dic)klistall(hTree)for i in k:print(i.data,i.code)if __name__ __main__:try:main()except Exception as e:print(您的输入不合法出错信息如下)print(e)4.5 单源最短路径
设置顶点集合S并不断地作贪心选择来扩充这个集合一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知初始时S中仅含有源。设u是G的某一个顶点把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路径长度的顶点u将u添加到S中同时对数组dist作必要的修改。一旦S包含了所有V中顶点dist就记录了从源到所有其他顶点之间的最短路径长度
4.6 最小生成树
设G (V,E)是无向连通带权图即一个网络。E中每条边(v,w)的权为c[v][w]。如果G的子图G’是一棵包含G的所有顶点的树则称G’为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中耗费最小的生成树称为G的最小生成树最小生成树性质MST性质设G(V,E)是连通带权图U是V的真子集。如果(u,v)∈E且u∈Uv∈V-U且在所有这样的边中(u,v)的权为c[u][v]最小那么一定存在G的一颗最小生成树它以(u,v)为其中一条边Prim算法 首先置S{1}然后只要S是V的真子集就作如下的贪心选择选取满足条件i∈Sj∈V-S且c[i][j]最小的边将顶点j添加到S中。这个过程一直进行到SV时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。 Copyright: Copyright (c) 2019
Author: Justlovesmile
Title: 最小生成树-Prim算法
def prim(n,c):#初始化Prim算法的数组s[1]p[1]lowcost[float(inf) for i in range(n)]m1#遍历S中的点for r in range(1,n):nslen(s)for t in range(ns):is[t]for j in range(1,n1):#如果不在S中且最短则记录if(j not in s) and (c[i][j]lowcost[m]):lowcost[m]c[i][j]kjuim1s.append(k)p.append(u)for i in range(1,len(s)):print(s[i],p[i],c[s[i]][p[i]])def main():#输入点数nint(input(Please input the number of points:\n))#初始化边长c[[float(inf) for i in range(n1)] for j in range(n1)]for i in range(1,n1):c[i][i]0if(n1):raise ValueError(fYou input {n} point.)#输入边长ginput(Please input the p1,p2 and weight,like: 1 2 4\nInput end to end.\n)while(g!end):ag.split()iint(a[0])jint(a[1])wfloat(a[2])c[i][j]wc[j][i]wginput(Please input the p1,p2 and weight,like: 1 2 4\nInput end to end.\n)prim(n,c)if __name____main__:try:main()except Exception as e:print(您的输入不合法出错信息如下)print(e)Kruskal算法 首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始依边权递增的顺序查看每一条边并按下述方法连接2个不同的连通分支 当查看到第k条边(v,w)时如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时就用边(v,w)将T1和T2连接成一个连通分支然后继续查看第k1条边如果端点v和w在当前的同一个连通分支中就直接再查看第k1条边。这个过程一直进行到只剩下一个连通分支时为止。 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ni9nWaiF-1596025346702)(https://s2.ax1x.com/2019/11/21/MIvIdP.png)] Copyright: Copyright (c) 2019
Author: Justlovesmile
Title: 最小生成树-Kruskal算法
class Edge:def __init__(self,u,v,w):self.uuself.vvself.wwclass EdgeNode:def __init__(self,p,g):self.idpself.ggdef kruskal(n,e):esorted(e,keylambda x: x.w)enlen(e)s[0]e[0].u.g,e[0].v.g0,0for j in range(en):if(j not in s) and (e[j].u.g!e[j].v.g):me[j].u.g if e[j].u.ge[j].v.g else e[j].v.gfor eachedge in e:if (eachedge.ue[j].u or eachedge.ve[j].v or eachedge.ue[j].v or eachedge.ve[j].u) and (eachedge.u.geachedge.v.g):mmin(eachedge.u.g,eachedge.v.g,m)eachedge.u.geachedge.v.gme[j].u.ge[j].v.gms.append(j)for i in range(len(s)):print(e[s[i]].u.id,e[s[i]].v.id,e[s[i]].w)def main():#输入点数nint(input(Please input the number of points:\n))if(n1):raise ValueError(fYou input {n} point.)#输入边长e[]p{}ginput(Please input the p1,p2 and weight,like: 1 2 4\nInput end to end.\n)aa,bbn,n1while(g!end):ag.split()i,j,wint(a[0]),int(a[1]),float(a[2])if(i not in p.keys()):p[i]EdgeNode(i,aa)if(j not in p.keys()):p[j]EdgeNode(j,bb)e.append(Edge(p[i],p[j],w))ginput(Please input the p1,p2 and weight,like: 1 2 4\nInput end to end.\n)aa1bb1kruskal(n,e)if __name____main__:try:main()except Exception as e:print(您的输入不合法出错信息如下)print(e)第五章 回溯法 回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在问题的解空间树中按深度优先策略从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时先判断该结点是否包含问题的解。如果肯定不包含则跳过对该节点为根的子树的搜索逐层向其祖先结点回溯否则进入该子树继续按深度优先策略搜索 具有剪枝函数的深度优先生成法 扩展结点正在产生儿子的结点称为扩展结点 活结点自身已生成但其儿子还没有全部生成的结点 回溯法的步骤 (1)针对所给问题定义问题的解空间 (2)确定易于搜索的解空间结构 (3)以深度优先方式搜索解空间并在搜索过程中用剪枝函数避免无效搜索 子集树当所给的问题是从n个元素的集合S中找出满足某种性质的子集时相应的解空间树称为子集树。通常有2n个叶子节点其节点总个数为2n1-1。如0-1背包问题 排列树当所给的问题是确定n个元素满足某种性质的排列时相应的解空间树称为排列树。排列树通常有n个叶子节点。如旅行售货员问题。 回溯算法的效率在很大程度上依赖于以下因素 (1)产生x[k]的时间 (2)满足显约束的x[k]值的个数 (3)计算约束函数constraint的时间 (4)计算上界函数bound的时间 (5)满足约束函数和上界函数约束的所有x[k]的个数。好的约束函数能显著地减少所生成的结点数。但这样的约束函数往往计算量较大。因此在选择约束函数时通常存在生成结点数与约束函数计算量之间的折衷。
5.2 装载问题 如果一个给定装载问题有解则采用下面的策略可得到最优装载方案。 (1)首先将第一艘轮船尽可能装满(2)将剩余的集装箱装上第二艘轮船。 解空间子集树 可行性约束函数(选择当前元素) 上界函数(不选择当前元素)当前载重量cw剩余集装箱的重量r≤当前最优载重量bestw Copyright: Copyright (c) 2019
Author: Justlovesmile
Title: 装载问题回溯法
def backtrack(i,c):global w,bestx,x,bestw,r,cwif(ilen(w)-1):if(cwbestw):for j in range(1,len(w)):bestx[j]x[j]bestwcwreturn ;#逐层搜索子树r-w[i]if(cww[i]c):x[i]1cww[i]backtrack(i1,c)cw-w[i]if(cwrbestw):x[i]0backtrack(i1,c)rw[i]def main():global w,bestx,x,bestw,r,cww[0]minput(Please input the weight of each items:(eg:1 2 3 4 5)\n).split()nlen(m) #物品数量if(n0):raise ValueError(物品数量不能为空)r0 #剩余的物品容量#转换w类型并初始化rfor i in range(n):w.append(int(m[i]))rw[i1]c1int(input(Please input the size of No.1 ship:\n)) #第一艘船载重量c2int(input(Please input the size of No.2 ship:\n)) #第二艘船载重量x[0 for i in range(n1)] #记录路径bestxx[:] #最优路径bestw,cw0,0 #最优载重量当前载重量#尽可能的装满第一个backtrack(1,c1)#print(bestx)cw20for i in range(1,len(bestx)):if(bestx[i]0):cw2w[i]if(cw2c2):print(不能由两艘船装完)return ;else:for i in range(1,len(bestx)):if(bestx[i]1):print(f第{i}个物品重量{w[i]},装入第1艘船)else:print(f第{i}个物品重量{w[i]},装入第2艘船)if __name__ __main__:try:main()except Exception as e:print(您的输入不合法出错信息如下)print(e)5.6 0-1背包问题
n3, C30, w{16, 15, 15}, v{45, 25, 25}[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MgfSxpG2-1596025346704)(https://s2.ax1x.com/2019/11/21/Mo9ygU.png)] Copyright: Copyright (c) 2019
Author: Justlovesmile
Title: 0-1背包问题回溯法
class Q:def __init__(self,_id,qq):self.id_idself.dqqdef bound(i):global bestp,cw,cp,n,p,c,w,x,bestxcleftc-cwboundcpwhile(in and w[i]cleft):cleft-w[i]boundp[i]i1#贪心if(in):boundp[i]*cleft/w[i]return bound def backtrack(i):global bestp,cw,cp,n,p,c,w,x,bestx#到达叶结点if(in):if(cpbestp):for j in range(1,n1):bestx[j]x[j]bestpcpreturn ;if(cww[i]c):x[i]1cww[i]cpp[i]backtrack(i1)cp-p[i]cw-w[i]if(bound(i1)bestp):x[i]0backtrack(i1)def main():global bestp,cw,cp,n,p,c,w,x,bestxppinput(Please input the price of each items.(eg:1 2 3 4 5)\n).split()wwinput(Please input the weight of each items.(eg:1 2 3 4 5)\n).split()if(len(pp)!len(ww)):raise ValueError(您的输入长度不一致)nlen(pp)cfloat(input(Please input the size of bag:\n))cw0 #当前重量cp0 #当前价值bestp0 #当前最优价值x[0 for i in range(n1)] #初始化临时选择方案bestxx[:] #初始化最优选择方案p[0] #价值列表w[0] #重量列表#单位重量价值#初始化q[Q(0,0) for i in range(n)] for i in range(n):pp[i]float(pp[i])ww[i]float(ww[i])q[i].dpp[i]/ww[i]q[i].idiqsorted(q,keylambda x:x.d)[::-1] #从大到小排序for i in range(n):p.append(pp[q[i].id])w.append(ww[q[i].id])#回溯backtrack(1)#打印输出print(Max price:,bestp,包括)for i in range(len(bestx)):if(bestx[i]1):print(f第{q[i-1].id1}个,价值{pp[q[i-1].id]},重量{ww[q[i-1].id]})if __name__ __main__:try:main()except Exception as e:print(您的输入不合法出错信息如下)print(e)第六章 分支限界法
分支限界法以广度优先或以最小耗费(最大效益)优先的方式搜索解空间树。其搜索策略是在扩展结点处先生成其所有儿子结点然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点加速搜索的进程在每一格活结点处计算一个函数值限界并根据函数值从当前活结点表中选择一个最有利的结点作为扩展结点使搜索朝着解空间上最优解的分支推进以便尽快找出一个最优解。常见两种分支限界法①队列式FIFO/LIFO分支限界法②优先队列式分支限界法与回溯法对比 1求解目标回溯法的求解目标是找出解空间树中满足约束条件的所有解而分支限界法的求解目标则是找出满足约束条件的一个解或是在满足约束条件的解中找出在某种意义下的最优解。2搜索方式的不同回溯法以深度优先的方式搜索解空间树而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Qyqak2qE-1596025346706)(https://s2.ax1x.com/2019/11/21/MoPuFI.png)]
6.5 0-1背包问题
class Q:def __init__(self,_id,qq):self.id_idself.dqqclass BBnode:def __init__(self,par,ch):self.parparself.chchclass HeapNode:def __init__(self,bNode,up,pp,ww,lev):self.liveNodebNodeself.upupself.pppself.wwwself.levlev#插入队列
def addlivenode(heap,up,pp,ww,lev,par,ch):bBBnode(par,ch)nodeHeapNode(b,up,pp,ww,lev)heap.append(node)#上界函数贪心
def bound(i):global cw,cp,n,p,c,wcleftc-cwboundcpwhile(in and w[i]cleft):cleft-w[i]boundp[i]i1if(in):boundp[i]*cleft/w[i]return bounddef knapsack():global bestp,cw,cp,n,p,c,w,bestxi1upbound(i)heap[]cnodeBBnode(None,None)while(i!n1):#左孩子cleftcww[i]if(cleftc):if(cpp[i]bestp):bestpcpp[i]addlivenode(heap,up,cpp[i],cww[i],i1,cnode,True)#右孩子upbound(i1)if(upbestp):addlivenode(heap,up,cpp[i],cww[i],i1,cnode,False)#取下一扩展结点nodeheap.pop(0)#更新数据cnodenode.liveNodecwnode.wcpnode.pupnode.upinode.lev#最优解for j in range(1,n1)[::-1]:bestx[j]1 if cnode.chTrue else 0cnodecnode.par实现 Copyright: Copyright (c) 2019
Author: Justlovesmile
Title: 0-1背包问题分支限界法
class Q:def __init__(self,_id,qq):self.id_idself.dqqclass BBnode:def __init__(self,par,ch):self.parparself.chchclass HeapNode:def __init__(self,bNode,up,pp,ww,lev):self.liveNodebNodeself.upupself.pppself.wwwself.levlev#插入队列
def addlivenode(heap,up,pp,ww,lev,par,ch):bBBnode(par,ch)nodeHeapNode(b,up,pp,ww,lev)heap.append(node)#上界函数贪心
def bound(i):global cw,cp,n,p,c,wcleftc-cwboundcpwhile(in and w[i]cleft):cleft-w[i]boundp[i]i1if(in):boundp[i]*cleft/w[i]return bounddef knapsack():global bestp,cw,cp,n,p,c,w,bestxi1upbound(i)heap[]cnodeBBnode(None,None)while(i!n1):#左孩子cleftcww[i]if(cleftc):if(cpp[i]bestp):bestpcpp[i]addlivenode(heap,up,cpp[i],cww[i],i1,cnode,True)#右孩子upbound(i1)if(upbestp):addlivenode(heap,up,cpp[i],cww[i],i1,cnode,False)#取下一扩展结点nodeheap.pop(0)#更新数据cnodenode.liveNodecwnode.wcpnode.pupnode.upinode.lev#最优解for j in range(1,n1)[::-1]:bestx[j]1 if cnode.chTrue else 0cnodecnode.pardef main():global bestp,cw,cp,n,p,c,w,bestx#输入ppinput(Please input the price of each items.(eg:1 2 3 4 5)\n).split()wwinput(Please input the weight of each items.(eg:1 2 3 4 5)\n).split()if(len(pp)!len(ww)):raise ValueError(您的输入长度不一致)nlen(pp)cfloat(input(Please input the size of bag:\n))cw0 #当前重量cp0 #当前价值bestp0 #当前最优价值bestx[0 for i in range(n1)] #最优解初始化p[0]w[0]q[Q(0,0) for i in range(n)] #单位重量价值allp0 #总价值allw0 #总重量#单位重量价值列表for i in range(n):pp[i]float(pp[i])ww[i]float(ww[i])allppp[i]allwww[i]q[i].dpp[i]/ww[i]q[i].idiqsorted(q,keylambda x:x.d)[::-1] #从大到小排序for i in range(n):p.append(pp[q[i].id])w.append(ww[q[i].id])#如果能直接全装if(allwc):print(fAll in! Total price is {allp}!)return ;knapsack()print(Max price:,bestp,包括)for i in range(len(bestx)):if(bestx[i]1):print(f第{q[i-1].id1}个,价值{pp[q[i-1].id]},重量{ww[q[i-1].id]})if __name__ __main__:try:main()except Exception as e:print(您的输入不合法!出错信息如下)print(e)6.6 装载问题 Copyright: Copyright (c) 2019
Author: Justlovesmile
Title: 装载问题分支限界法
class Node:def __init__(self,parent,isleftchild,weight):self.parentparentself.islchildisleftchildself.weightweightdef maxloading(c):global w,bestx,bestw,r,cw,ni1r-w[i]cnodeNode(None,None,-1) #当前结点q[cnode]while(True):#左结点cleftcww[i]if(cleftc):enodeNode(cnode,True,cleft)if(cleftbestw):bestwcleft bestxenodeif(in):q.append(enode)if(in):return;#右结点if(cwrbestw and in):enodeNode(cnode,False,cw)q.append(enode)#出队列cnodeq.pop(0)cwcnode.weightif(cw-1):if(len(q)0):return ;q.append(Node(None,None,-1))cnodeq.pop(0)cwcnode.weighti1r-w[i]def main():global w,bestx,bestw,r,cw,nw[0]minput(Please input the weight of each items:(eg:1 2 3 4 5)\n).split()nlen(m) #物品数量if(n0):raise ValueError(物品数量不能为空)r0 #剩余的物品容量bestw,cw0,0#转换w类型并初始化rfor i in range(n):w.append(int(m[i]))rw[i1]allweightr #总重量x[0 for i in range(n1)]tx[]c1int(input(Please input the size of No.1 ship:\n)) #第一艘船载重量c2int(input(Please input the size of No.2 ship:\n)) #第二艘船载重量maxloading(c1)if(bestwc2allweight):print(不能由两艘船装完)return;for i in range(1,n1)[::-1]:if(bestx.islchildTrue):tx.append(1)elif(bestx.islchildFalse):tx.append(0)bestxbestx.parentfor i in range(len(tx)):x[i1]tx[::-1][i]print(f第一艘船载重量{bestw}包括)for i in range(1,n1):if(x[i]1):print(f第{i}个集装箱)print(f第二艘船载重量{allweight-bestw},包括)for i in range(1,n1):if(x[i]0):print(f第{i}个集装箱) if __name__ __main__:try:main()except Exception as e:print(您的输入不合法出错信息如下)print(e)算法的特征输入输出确定性有限性θ记号在算法复杂性的表示法中表示紧致界由分治法产生的子问题往往是原问题的较小模式这就为使用递归提供了方便建立计算模型的目的为了使问题的计算复杂性分析有一个共同的客观尺度基本计算模型RAM,RASP,TM拉斯维加斯算法找到的解一定是正确的贪心算法常采用自顶向下的方式求解最优解采用高级语言的主要好处 ①更接近算法语言易学易掌握 ②提供了结构化程序设计的环境和工具使得设计出的程序可读性高可维护性强可靠性高 ③不依赖于机器语言因此写出的程序可移植性好重用率高 ④自动化程度高开发周期短程序员可以集中精力从事更重要的创造性劳动提高程序质量 贪心算法的特点 ①不能保证最后求得的解是最优的 ②策略易发现运用简单被广泛运用 ③策略多样结果也多样 ④常用到辅助算法排序 平衡子问题思想通常分治法在分割原问题形成若干子问题时这些子问题的规模都大致相同 Prim算法采用贪心策略求解最小生成树问题其时间复杂度是O(n^2)。 动态规划算法适用于解具有某种最优性质的问题。 贪心算法做出的选择只是适用于在某种意义上的局部最优选择 在动态规划算法中通常不同子问题的个数随问题规模呈多项式级增长 动态规划是解决多阶段决策过程的最优化问题 选择能产生最优解的贪心准则是设计贪心算法的核心问题 分支限界法常以广度优先或以最小耗费最大效益优先的方式搜索问题的解空间树 为什么用分治法设计的算法一般有递归调用因为子问题的规模还很大时必须继续使用分治法反复分治必然要用到递归 请简述分支限界法找最优解比回溯法高的原因在分支限界法中每一个点只有一次机会称为扩展结点。 回溯法的算法框架按照问题的解空间一般分为子集树算法框架如解0-1背包问题和排列树算法框架如解批处理作业调度问题 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Nqgp8sFu-1596025346708)(https://s2.ax1x.com/2019/11/21/MIEmhn.png)] 常见的多项式阶O(1) O(logn) O(n) O(nlogn) O(n^2) O(n^3) O(2^n) O(n!) O(n^n) 回溯和分支限界 相同点都是以构造一颗状态空间树为基础的树的结点反映了对一部分解所作的特定选择不同点①他们处理的问题类型不同回溯法的求解目标是找出T中满足约束条件的所有解而分支限界法的求解目标则是找出满足约束条件的一个解或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解即在某种意义下的最优解。②生成状态空间树的顺序不同③对节点存储的常用数据结构以及节点存储特性也各不相同除由搜索方式决定的不同的存储结构外分支限界法通常需要存储一些额外的信息以利于进一步地展开搜索 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UrbrkTHf-1596025346710)(https://s2.ax1x.com/2019/11/21/MoFWQK.png)] NP问题是指还未被证明是否存在多项式算法能够解决的问题而其中NP完全问题又是最有可能不是P问题的问题类型。所有的NP问题都可以用多项式时间划归到他们中的一个。所以显然NP完全的问题具有如下性质它可以在多项式时间内求解当且仅当所有的其他的NP完全问题也可以在多项式时间内求解。
