本文共 32819 字,大约阅读时间需要 109 分钟。
对于T(N),如果存在~T(N),使得当N→∞时有(T(N)-~T(N))/T(N)→0,那么就说~T(N)是T(N)当N→∞时的渐进性态。
递归函数
边界条件
和递归方程
#includeusing namespace std;int factorial(int n){ if(n==0) return 1; else{ return n*factorial(n-1); }}
#includeusing namespace std;int fibonacci(int n){ if(n<=1) return 1; else return fibonacci(n-1)+fibonacci(n-2);}
def hanoi(n,a,b,c): #将a上的n个圆盘经过c移动到b if(n>0): hanoi(n-1,a,c,b) move(a,b) hanoi(n-1,c,b,a)
递归算法的优点:结构清晰,可读性强,容易用数学归纳法来证明算法的正确性
递归算法的缺点:运行效率低,无论是耗费的计算时间还是占用的存储空间都比非递归算法多。
消除递归的方法:①采用一个用户定义的栈来模拟系统的递归调用工作栈,从而达到将递归算法改为非递归算法的目的②用递推来实现递归函数
分解
为k个规模较小的子问题,这些子问题相互独立
且与原问题相同
。递归地解这些子问题,然后将各子问题的解合并
得到原问题的解。def binarySearch(a,x): #a是数组,x是要搜索的数 a=sorted(a) #a要求有序(从小到大) n=len(a) left,right=0,n-1 while(left<=right): middle=(left+right)//2 if(x==a[middle]): return middle elif(x>a[middle]): left=middle+1 else: right=middle-1 #未找到 return -1
X=[A][B],Y=[C][D],其中X,Y有n位;A,B,C,D均有n/2位由此可以得到:X=A*2^(n/2)+B , Y=C*2^(n/2)+DXY=(A*2^(n/2)+B)(C*2^(n/2)+D) =A*C*2^n+(A*D+C*B)*2^(n/2)+B*D =A*C*2^n+((A-B)(D-C)+A*C+B*D)*2^(n/2)+B*D最后一个式子看起来似乎复杂了,但是它仅需做3次n/2位整数的乘法,6次加减法和2次移位
(n/2)*(n/2)
的方阵def merge(arr,left,mid,right): #left,right为需要合并的数组范围 #mid为中间下标,左边比中值小,右边比中值大 i=left j=mid+1 #复制一个临时数组 aux=arr[:] for k in range(left,right+1): #如果左指针超过mid,即右边还有剩余 if(i>mid): arr[k]=aux[j] j=j+1 #如果右指针超过right,即左边还有剩余 elif(j>right): arr[k]=aux[i] i=i+1 #如果左边小,则左边合并 elif(aux[i]=right): return ; #取中值,拆成左右两边 mid=(left+right)//2 #对左半边进行归并排序 mergeSort(arr,left,mid) #对右半边进行归并排序 mergeSort(arr,mid+1,right) #合并算法 merge(arr,left,mid,right)
def quicksort(arr,low,high): if low=temp)): high=high-1 #此时右指针对应值小于标准值,将其复制给左指针位置 arr[low]=arr[high] #当左边小于标准值,左指针右移 while((low <=temp)): low=low+1 #此时左指针对应值大于标准值,将其复制给右指针位置 arr[high]=arr[low] #将标准值赋值给左右指针相遇的位置 arr[low]=temp #此时low左边全部小于等于arr[low],low右边全部大于等于arr[low] return low
"""Copyright: Copyright (c) 2019Author: JustlovesmileTitle: 最近点对问题"""#按x坐标排序的点class Point1: #x,y为坐标,id为序号 def __init__(self,xx,yy,index): self.x=xx self.y=yy self.id=index#按y坐标排序的点class Point2(Point1): #x,y为坐标,id为该点按x排序时的序号 def __init__(self,xx,yy,index): self.x=xx self.y=yy self.id=index #表示输出的平面点对class Pair: #a,b为点,dist为距离 def __init__(self, aa, bb,dd): self.a=aa self.b=bb self.dist=dd #求平面上任意两点u,v的距离def dist(u,v): dx=u.x-v.x dy=u.y-v.y return dx*dx+dy*dy#归并排序def merge(S,order,left,mid,right): i=left j=mid+1 aux=S[:] #按x排序 if(order=='x'): for k in range(left,right+1): if(i>mid): S[k]=aux[j] j=j+1 elif(j>right): S[k]=aux[i] i=i+1 elif(S[i].xmid): S[k]=aux[j] j=j+1 elif(j>right): S[k]=aux[i] i=i+1 elif(S[i].y =right): return ; mid=(left+right)//2 mergeSort(S,x,left,mid) mergeSort(S,x,mid+1,right) merge(S,x,left,mid,right)#计算最接近点对def closePair(S,Y,Z,l,r): #两个点 if(r-l==1): return Pair(S[l],S[r],dist(S[l],S[r])) #三个点 if(r-l==2): d1=dist(S[l],S[l+1]) d2=dist(S[l+1],S[r]) d3=dist(S[l],S[r]) if((d1<=d2)and(d1<=d3)): return Pair(S[l],S[l+1],d1) if(d2<=d3): return Pair(S[l+1],S[r],d2) else: return Pair(S[l],S[r],d3) #多于三个点 m=(l+r)//2 f=l g=m+1 for i in range(l,r+1): if(Y[i].id>m): Z[g]=Y[i] g=g+1 else: Z[f]=Y[i] f=f+1 #递归求解 best = closePair(S,Z,Y,l,m) right = closePair(S,Z,Y,m+1,r) #选最近的点对 if(right.dist
最优子结构
与重叠子问题
"""Copyright: Copyright (c) 2019Author: JustlovesmileTitle: 矩阵连乘问题"""#计算最优值def matrixChain(p,m,s): #m[i][j]表示A[i]到A[j]所需的最少数乘次数 #s[i][j]表示A[i]到A[j]所需的最少数乘法对应的分隔位置 n=len(p)-1 for r in range(2,n+1): for i in range(1,n-r+2): #沿斜线方向递进 j=r+i-1 m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j] s[i][j]=i k=i+1 #寻找i到j间最优分隔k while(k=1): if(y!=int(s[0])): raise ValueError("您输入的矩阵不能相乘!") x,y=int(s[0]),int(s[1]) p.append(x) p.append(y) m=[] s=[] for i in range(n+1): m.append([0]*(n+1)) s.append([0]*(n+1)) 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)
"""Copyright: Copyright (c) 2019Author: JustlovesmileTitle: 最长公共子序列问题"""def IcsLength(x,y,b): m=len(x) n=len(y) #初始化 c=[] for j in range(m+1): c.append([0]*(n+1)) #逐个比较 for i in range(1,m+1): for j in range(1,n+1): #如果相等那么此时的最长公共长度为去除该位置的最长公共长度+1 if(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]=2 else: c[i][j]=c[i][j-1] b[i][j]=3 return c[m][n]#根据b[i][j]输出最长子序列def Ics(i,j,x,b): if(i==0 or j==0): return ; #如果是第一类子问题的解,则说明该位置是公共部分 if(b[i][j]==1): Ics(i-1,j-1,x,b) print(x[i-1],end="") #如果是第二类子问题的解,则说明此时Zk≠Xm elif(b[i][j]==2): Ics(i-1,j,x,b) #Zk≠Yn else: Ics(i,j-1,x,b)def main(): #输入字符串 A=input("Please input No.1 Ics:").split() B=input("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)
"""Copyright: Copyright (c) 2019Author: JustlovesmileTitle: 凸多边形最优三角剖分问题"""from isConvex import isConvex#计算最优值def minWeightTriangulation(n,t,s,v): #t[i][j]是凸子多边形vi-1,vi,...,vj的最优三角剖分对应的权函数值 for r in range(2,n+1): for i in range(1,n-r+2): j=r+i-1 t[i][j]=t[i+1][j]+weight(i-1,i,j,v) s[i][j]=i k=i+1 #遍历i到j的所有边 while(k
判断是否为凸多边形
#判断是否为凸多边形'''计算直线表达式param vertex1: 前一个顶点param vertex2: 后一个顶点return (type, param): 返回直线的类别及其描述参数'''def kb(vertex1, vertex2): x1 = vertex1[0] y1 = vertex1[1] x2 = vertex2[0] y2 = vertex2[1] if x1==x2: return (0, x1) # 0-垂直直线 if y1==y2: return (1, y1) # 1-水平直线 else: k = (y1-y2)/(x1-x2) b = y1 - k*x1 return (2, k, b) # 2-倾斜直线'''判断是否为凸多边形param vertexes: 构成多边形的所有顶点坐标列表,如[[0,0], [50, 0], [0, 50]]return convex: 布尔类型,为True说明该多边形为凸多边形,否则为凹多边形'''def isConvex(vertexes): # 默认为凸多边形 convex = True # 多边形至少包含三个顶点 l = len(vertexes) if l<3: raise ValueError("多边形至少包含三个顶点!") # 对每两个点组成的直线做判断 for i in range(l): pre = i nex = (i+1)%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*s<0: convex = False break if convex==False: break if convex==False: break # 打印判断结果 if convex==True: print("该多边形为凸多边形!") else: print("该多边形为凹多边形!") return convex
"""Copyright: Copyright (c) 2019Author: JustlovesmileTitle: 0-1背包问题--动态规划"""#跳跃点法def knapsack_Pro(n,v,w,C,p,x): #head指向每一阶段跳跃点集合的开始 head=[0 for i in range(n+1)] p[0][0],p[0][1]=0,0 left,right,pnext,head[1]=0,0,1,1 for i in range(n): k=left for j in range(left,right+1): if(p[j][0]+w[i]>C): break y=p[j][0]+w[i] m=p[j][1]+v[i] #重量小于此数的跳跃点直接加进来,不会被支配 while(k<=right and p[k][0]p[pnext-1][1]): p[pnext][0]=y p[pnext][1]=m pnext+=1 #取出可以支配的点 while(k<=right and p[k][1]<=p[pnext-1][1]): k+=1 #上面break后 while(k<=right): p[pnext][0]=p[k][0] p[pnext][1]=p[k][1] pnext+=1 k+=1 left=right+1 right=pnext-1 head[i+1]=pnext traceback_Pro(n,w,v,p,head,x)def traceback_Pro(n,w,v,p,head,x): j=p[head[n]-1][0] m=p[head[n]-1][1] print("max value:",m,"max weight:",j) for i in range(n)[::-1]: for k in range(head[i],head[i+1]-1): if(p[k][0]+w[i]==j and p[k][1]+v[i]==m): x[i]=1 j=p[k][0] m=p[k][1] breakdef knapsack(v,w,C,m): #m[i][j]指背包容量为j,可选择物品为i,i+1,...,n时的0-1背包问题的最优值 n=len(v)-1 #只剩一个物品的情况 for j in range(C): m[n][j] = v[n] if j>=min(w[n]-1,C) else 0 #普通情况 for i in range(1,n)[::-1]: for j in range(C): m[i][j] = max(m[i+1][j],m[i+1][j-w[i]]+v[i]) if j>w[i]-1 else m[i+1][j] #第一件物品 if(n>0): m[0][C-1]=m[1][C-1] if C-1>=w[0]: m[0][C-1]=max(m[0][C-1],m[1][C-1-w[0]]+v[0])def traceback(m,w,C,x): c=C-1 for i in range(len(w)-1): #没选物品i则x[i]=0 if (m[i][c]==m[i+1][c]): x[i]=0 else: x[i]=1 c -= w[i] #对于最后一个物品 x[len(w)-1]=1 if m[len(w)-1][c]>0 else 0#输出格式def cout(x,v,w): total_v=0 total_w=0 print("Choose:") for i in range(len(v)): if x[i]==1: print(f"No.{i+1} item: value is {v[i]} , weight is {w[i]}") total_v +=v[i] total_w +=w[i] print(f"total value: {total_v}") print(f"total weight: {total_w}")def main(): v=[] #物品的价值列表 w=[] #物品的重量列表 #输入物品数量 n=input("Please input the number of items:\n") if(n=="" or n=="0"): raise ValueError("您输入了空值或0!") else: n=int(n) x=[0 for i in range(n+1)] #选择两种算法(课本上的) ans=input("Choose Knapsack or Knapsack_Pro?(1 or 2)\n").split()[0] if ans=='1': m=[] #m(i,j)指背包容量为j,可选择物品为i,i+1,...,n时的0-1背包问题的最优值 for i in range(n): item=input(f"please input No.{i+1} item's value(v) and weight(w):(eg:v w)\n").split() v.append(int(item[0])) w.append(int(item[1])) C=int(input("Please input the max weight of bag:\n")) if(C<=0): 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 ans=='2': for i in range(n): item=input(f"please input No.{i+1} item's 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)] C=float(input("Please input the max weight of bag:\n")) if(C<=0): raise ValueError("背包容量不能小于等于0") if(n==1): if(w[0]<=C): x[0]=1 else: x[0]=0 else: 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)
"""Copyright: Copyright (c) 2019Author: JustlovesmileTitle: 活动安排问题"""#活动类,每个活动包括开始时间和结束时间class activity(): def __init__(self,ss,ff): self.s=ss self.f=ff def greedySelector(arr,a): n=len(arr)-1 a[0]=True j=0 count=1 #满足开始时间大于上一个活动的结束时间的加入(设为True) #O(n) for i in range(1,n+1): if(arr[i].s>=arr[j].f): a[i]=True j=i count+=1 else: a[i]=False return countdef main(): activities=[] #输入数据 n=int(input("please input the number of activities:\n")) #异常处理 if(n==0): raise ValueError("您输入了0!") print("Use greedy selector , activities should be ordered by the end_time.") for i in range(n): item=input("please input the begin-time and end-time:(eg: 3 6)\n").split() if(len(item)!=2): raise ValueError("您输入的数据个数不合法!") s=activity(float(item[0]),float(item[1])) activities.append(s) #以结束时间非减序排序 activities=sorted(activities,key=lambda x:x.f) #初始化选择集合a a=[False for i in range(n)] count=greedySelector(activities,a) print("Maximum number of activities:",count) print("Choose:",a)if __name__ == "__main__": try: main() except Exception as e: print("您的输入不合法!出错信息如下:") print(e)
#构建二叉树类型class BinaryTree: def __init__(self,data,left,right,code): self.data=data self.left=left self.right=right self.code=code def getdata(self): return self.data#哈夫曼树class Huffman: def __init__(self,tree,ww): self.tree=tree self.w=ww def getweight(self): return self.wdef huffmanTree(f): #f是出现频率权值字典 H=[] n=len(f) #根据value对键进行从大到小排序 for i in sorted(f,key=f.__getitem__,reverse=True): tree = BinaryTree(i,0,0,"") w = Huffman(tree,f[i]) H.append(w) for i in range(1,n): #取出最后两位 x=H.pop() y=H.pop() #取权重小的做左孩子,大的是右孩子 t=BinaryTree(i,x.tree if x.wx.w else x.tree,"") h=Huffman(t,x.w+y.w) H.append(h) #根据权重从大到小排序 H=sorted(H,key=lambda x:x.w,reverse=True) return H.pop()
"""Copyright: Copyright (c) 2019Author: Justlovesmile Title: 哈夫曼编码"""#构建二叉树类型class BinaryTree: def __init__(self,data,left,right,code): self.data=data self.left=left self.right=right self.code=code def getdata(self): return self.data#哈夫曼树class Huffman: def __init__(self,tree,ww): self.tree=tree self.w=ww def getweight(self): return self.w #计算权重def makedict(s): dic={ } for i in s: if i not in dic.keys(): dic[i]=1 else: dic[i]+=1 return dicdef huffmanTree(f): #f是出现频率权值字典 H=[] n=len(f) #根据value对键进行从大到小排序 for i in sorted(f,key=f.__getitem__,reverse=True): tree = BinaryTree(i,0,0,"") w = Huffman(tree,f[i]) H.append(w) for i in range(1,n): #取出最后两位 x=H.pop() y=H.pop() #取权重小的做左孩子,大的是右孩子 t=BinaryTree(i,x.tree if x.wx.w else x.tree,"") h=Huffman(t,x.w+y.w) H.append(h) #根据权重从大到小排序 H=sorted(H,key=lambda x:x.w,reverse=True) return H.pop()def listall(h): m=[] k=[] left,right=h.tree.left,h.tree.right rcode="1" lcode="0" m.append(right) right.code+=rcode m.append(left) left.code+=lcode while(len(m)>0): #如果存在左孩子(左右必同时存在) if(m[-1].left): a=m.pop() c=a.code m.append(a.right) a.right.code=c+rcode m.append(a.left) a.left.code=c+lcode else: b=m.pop() k.append(b) return kdef back(hfmcode,filename): ans=input(f"Do you want to decode '{filename}'?(y/n)\n") if(ans!="y" and ans!='Y'): return; #读取要解压缩的文件 with open(filename,'r') as f: s=f.read() st="" #键和值交换形成新字典 new_dict = { v:k for k,v in hfmcode.items()} #写入新文件 with open('解压缩.txt','w') as f: for i in s: st+=i if(st in hfmcode.values()): f.write(new_dict[st]) st="" print("=="*10) print("ok!Please check the file: '解压缩.txt'") print("=="*10)def main(): filename1="测试用例.txt" filename2='编码后.txt' #可以选择读文件和输入字符串 s=input(f"Do you want to search {filename1}!(y/n)\n") if(s=="y" or s=="Y"): #读文件 with open(filename1,'r') as f: s=f.read() #权值字典 dic=makedict(s) print("权值:",dic) #构建哈夫曼树 hTree=huffmanTree(dic) #编码 k=listall(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: string=hfmcode[i] f.write(string) print("=="*10) print(f"ok!Please check the file: '{filename2}'") print("=="*10) back(hfmcode,filename2) else: s=input("Please input the string:") dic=makedict(s) print(dic) hTree=huffmanTree(dic) k=listall(hTree) for i in k: print(i.data,i.code)if __name__ == "__main__": try: main() except Exception as e: print("您的输入不合法!出错信息如下:") print(e)
c[v][w]
。如果G的子图G’是一棵包含G的所有顶点的树,则称G’为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中,耗费最小的生成树称为G的最小生成树c[u][v]
最小,那么一定存在G的一颗最小生成树,它以(u,v)为其中一条边c[i][j]
最小的边,将顶点j添加到S中。这个过程一直进行到S=V时为止。"""Copyright: Copyright (c) 2019Author: JustlovesmileTitle: 最小生成树-Prim算法"""def prim(n,c): #初始化Prim算法的数组 s=[1] p=[1] lowcost=[float('inf') for i in range(n)] m=1 #遍历S中的点 for r in range(1,n): ns=len(s) for t in range(ns): i=s[t] for j in range(1,n+1): #如果不在S中,且最短则记录 if(j not in s) and (c[i][j]
"""Copyright: Copyright (c) 2019Author: JustlovesmileTitle: 最小生成树-Kruskal算法"""class Edge: def __init__(self,u,v,w): self.u=u self.v=v self.w=wclass EdgeNode: def __init__(self,p,g): self.id=p self.g=g def kruskal(n,e): e=sorted(e,key=lambda x: x.w) en=len(e) s=[0] e[0].u.g,e[0].v.g=0,0 for j in range(en): if(j not in s) and (e[j].u.g!=e[j].v.g): m=e[j].u.g if e[j].u.g
回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时,先判断该结点是否包含问题的解。如果肯定不包含,则跳过对该节点为根的子树的搜索,逐层向其祖先结点回溯,否则,进入该子树,继续按深度优先策略搜索
具有剪枝函数的深度优先生成法
扩展结点:正在产生儿子的结点称为扩展结点
活结点:自身已生成但其儿子还没有全部生成的结点
回溯法的步骤:
子集树:当所给的问题是从n个元素的集合S中找出满足某种性质的子集时,相应的解空间树称为子集树。通常有2n个叶子节点,其节点总个数为2n+1-1。如:0-1背包问题
排列树:当所给的问题是确定n个元素满足某种性质的排列时,相应的解空间树称为排列树。排列树通常有n!个叶子节点。如:旅行售货员问题。
回溯算法的效率在很大程度上依赖于以下因素:
"""Copyright: Copyright (c) 2019Author: JustlovesmileTitle: 装载问题(回溯法)"""def backtrack(i,c): global w,bestx,x,bestw,r,cw if(i>len(w)-1): if(cw>bestw): for j in range(1,len(w)): bestx[j]=x[j] bestw=cw return ; #逐层搜索子树 r-=w[i] if(cw+w[i]<=c): x[i]=1 cw+=w[i] backtrack(i+1,c) cw-=w[i] if(cw+r>bestw): x[i]=0 backtrack(i+1,c) r+=w[i]def main(): global w,bestx,x,bestw,r,cw w=[0] m=input("Please input the weight of each items:(eg:1 2 3 4 5)\n").split() n=len(m) #物品数量 if(n==0): raise ValueError("物品数量不能为空!") r=0 #剩余的物品容量 #转换w类型并初始化r for i in range(n): w.append(int(m[i])) r+=w[i+1] c1=int(input("Please input the size of No.1 ship:\n")) #第一艘船载重量 c2=int(input("Please input the size of No.2 ship:\n")) #第二艘船载重量 x=[0 for i in range(n+1)] #记录路径 bestx=x[:] #最优路径 bestw,cw=0,0 #最优载重量,当前载重量 #尽可能的装满第一个 backtrack(1,c1) #print(bestx) cw2=0 for i in range(1,len(bestx)): if(bestx[i]==0): cw2+=w[i] if(cw2>c2): 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)
"""Copyright: Copyright (c) 2019Author: JustlovesmileTitle: 0-1背包问题(回溯法)"""class Q: def __init__(self,_id,qq): self.id=_id self.d=qqdef bound(i): global bestp,cw,cp,n,p,c,w,x,bestx cleft=c-cw bound=cp while(i<=n and w[i]<=cleft): cleft-=w[i] bound+=p[i] i+=1 #贪心 if(i<=n): bound+=p[i]*cleft/w[i] return bound def backtrack(i): global bestp,cw,cp,n,p,c,w,x,bestx #到达叶结点 if(i>n): if(cp>bestp): for j in range(1,n+1): bestx[j]=x[j] bestp=cp return ; if(cw+w[i]bestp): x[i]=0 backtrack(i+1) def main(): global bestp,cw,cp,n,p,c,w,x,bestx pp=input("Please input the price of each items.(eg:1 2 3 4 5)\n").split() ww=input("Please input the weight of each items.(eg:1 2 3 4 5)\n").split() if(len(pp)!=len(ww)): raise ValueError("您的输入长度不一致!") n=len(pp) c=float(input("Please input the size of bag:\n")) cw=0 #当前重量 cp=0 #当前价值 bestp=0 #当前最优价值 x=[0 for i in range(n+1)] #初始化临时选择方案 bestx=x[:] #初始化最优选择方案 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].d=pp[i]/ww[i] q[i].id=i q=sorted(q,key=lambda 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].id+1}个,价值:{pp[q[i-1].id]},重量:{ww[q[i-1].id]}")if __name__ == "__main__": try: main() except Exception as e: print("您的输入不合法!出错信息如下:") print(e)
广度优先
或以最小耗费(最大效益)优先
的方式搜索解空间树。其搜索策略是:在扩展结点处,先生成其所有儿子结点,然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点,加速搜索的进程,在每一格活结点处,计算一个函数值(限界),并根据函数值,从当前活结点表中,选择一个最有利的结点作为扩展结点,使搜索朝着解空间上最优解的分支推进,以便尽快找出一个最优解。class Q: def __init__(self,_id,qq): self.id=_id self.d=qqclass BBnode: def __init__(self,par,ch): self.par=par self.ch=chclass HeapNode: def __init__(self,bNode,up,pp,ww,lev): self.liveNode=bNode self.up=up self.p=pp self.w=ww self.lev=lev#插入队列def addlivenode(heap,up,pp,ww,lev,par,ch): b=BBnode(par,ch) node=HeapNode(b,up,pp,ww,lev) heap.append(node)#上界函数,贪心def bound(i): global cw,cp,n,p,c,w cleft=c-cw bound=cp while(i<=n and w[i]<=cleft): cleft-=w[i] bound+=p[i] i+=1 if(i<=n): bound+=p[i]*cleft/w[i] return bounddef knapsack(): global bestp,cw,cp,n,p,c,w,bestx i=1 up=bound(i) heap=[] cnode=BBnode(None,None) while(i!=n+1): #左孩子 cleft=cw+w[i] if(cleftbestp): bestp=cp+p[i] addlivenode(heap,up,cp+p[i],cw+w[i],i+1,cnode,True) #右孩子 up=bound(i+1) if(up>=bestp): addlivenode(heap,up,cp+p[i],cw+w[i],i+1,cnode,False) #取下一扩展结点 node=heap.pop(0) #更新数据 cnode=node.liveNode cw=node.w cp=node.p up=node.up i=node.lev #最优解 for j in range(1,n+1)[::-1]: bestx[j]=1 if cnode.ch==True else 0 cnode=cnode.par
实现
"""Copyright: Copyright (c) 2019Author: JustlovesmileTitle: 0-1背包问题(分支限界法)"""class Q: def __init__(self,_id,qq): self.id=_id self.d=qqclass BBnode: def __init__(self,par,ch): self.par=par self.ch=chclass HeapNode: def __init__(self,bNode,up,pp,ww,lev): self.liveNode=bNode self.up=up self.p=pp self.w=ww self.lev=lev#插入队列def addlivenode(heap,up,pp,ww,lev,par,ch): b=BBnode(par,ch) node=HeapNode(b,up,pp,ww,lev) heap.append(node)#上界函数,贪心def bound(i): global cw,cp,n,p,c,w cleft=c-cw bound=cp while(i<=n and w[i]<=cleft): cleft-=w[i] bound+=p[i] i+=1 if(i<=n): bound+=p[i]*cleft/w[i] return bounddef knapsack(): global bestp,cw,cp,n,p,c,w,bestx i=1 up=bound(i) heap=[] cnode=BBnode(None,None) while(i!=n+1): #左孩子 cleft=cw+w[i] if(cleftbestp): bestp=cp+p[i] addlivenode(heap,up,cp+p[i],cw+w[i],i+1,cnode,True) #右孩子 up=bound(i+1) if(up>=bestp): addlivenode(heap,up,cp+p[i],cw+w[i],i+1,cnode,False) #取下一扩展结点 node=heap.pop(0) #更新数据 cnode=node.liveNode cw=node.w cp=node.p up=node.up i=node.lev #最优解 for j in range(1,n+1)[::-1]: bestx[j]=1 if cnode.ch==True else 0 cnode=cnode.pardef main(): global bestp,cw,cp,n,p,c,w,bestx #输入 pp=input("Please input the price of each items.(eg:1 2 3 4 5)\n").split() ww=input("Please input the weight of each items.(eg:1 2 3 4 5)\n").split() if(len(pp)!=len(ww)): raise ValueError("您的输入长度不一致!") n=len(pp) c=float(input("Please input the size of bag:\n")) cw=0 #当前重量 cp=0 #当前价值 bestp=0 #当前最优价值 bestx=[0 for i in range(n+1)] #最优解初始化 p=[0] w=[0] q=[Q(0,0) for i in range(n)] #单位重量价值 allp=0 #总价值 allw=0 #总重量 #单位重量价值列表 for i in range(n): pp[i]=float(pp[i]) ww[i]=float(ww[i]) allp+=pp[i] allw+=ww[i] q[i].d=pp[i]/ww[i] q[i].id=i q=sorted(q,key=lambda x:x.d)[::-1] #从大到小排序 for i in range(n): p.append(pp[q[i].id]) w.append(ww[q[i].id]) #如果能直接全装 if(allw
"""Copyright: Copyright (c) 2019Author: JustlovesmileTitle: 装载问题(分支限界法)"""class Node: def __init__(self,parent,isleftchild,weight): self.parent=parent self.islchild=isleftchild self.weight=weightdef maxloading(c): global w,bestx,bestw,r,cw,n i=1 r-=w[i] cnode=Node(None,None,-1) #当前结点 q=[cnode] while(True): #左结点 cleft=cw+w[i] if(cleft<=c): enode=Node(cnode,True,cleft) if(cleft>bestw): bestw=cleft bestx=enode if(ibestw and i
输入,输出,确定性,有限性
紧致界
原问题的较小模式
,这就为使用递归
提供了方便为了使问题的计算复杂性分析有一个共同的客观尺度
RAM
,RASP
,TM
正确
的自顶向下
的方式求解最优解①更接近算法语言,易学,易掌握②提供了结构化程序设计的环境和工具,使得设计出的程序可读性高,可维护性强,可靠性高③不依赖于机器语言,因此写出的程序可移植性好,重用率高③自动化程度高,开发周期短,程序员可以集中精力从事更重要的创造性劳动,提高程序质量
①不能保证最后求得的解是最优的②策略易发现,运用简单,被广泛运用③策略多样,结果也多样④常用到辅助算法:排序
平衡子问题
思想:通常分治法在分割原问题,形成若干子问题时,这些子问题的规模都大致相同贪心策略
求解最小生成树问题
,其时间复杂度是O(n^2)。某种最优性质
的问题。局部最优
选择多项式
级增长多阶段决策过程
的最优化问题选择能产生最优解的贪心准则
是设计贪心算法的核心问题广度优先
或以最小耗费(最大效益)优先
的方式搜索问题的解空间树子集树
算法框架(如解0-1背包问题)和排列树
算法框架(如解批处理作业调度问题)O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
转载地址:http://mbgwi.baihongyu.com/