- 博客(7)
- 收藏
- 关注
原创 背包问题详解
请利用动态规划算法、回溯法、分支限界法、蒙特卡洛算法以及融合回溯法的蒙特卡洛算法来求解0-1背包问题,利用贪心算法来实现特殊类型的0-1背包问题,比较不同算法的时间复杂度和空间复杂度。import randomimport sysimport timeimport heapqimport numpy as npsys.setrecursionlimit(100000) # 递归...
2018-05-31 01:24:19
2260
1
原创 最长公共子序列算法python
动态规划(空间优化):def LCS(a, b): """ 最长公共子序列 空间复杂度为O(min(a,b))+1 记录左上角值""" if len(a) < len(b): a, b = b, a print(a, b) list = [0 for i in range(len(b))] for i in range(len(a))...
2018-05-31 01:16:10
401
原创 二维空间最近点对问题 python
给定n个二维空间中的点(x1,y1)(x2,y2)...(xn,yn),设计一个寻找两点之间距离最近的点对的算法,并分析算法时间复杂度暴力求解:import randomimport numpyimport mathimport timeimport matplotlib.pyplot as pltimport image# 暴力求解最近点对问题n = 500closest_p...
2018-05-31 01:04:22
5487
2
原创 排序算法性能比较 python
冒泡排序、选择排序堆排序、归并排序、快速排序计数排序import jsonimport randomimport timeimport matplotlibimport pandasdef Bubble_Sort(num): # 冒泡排序 for i in range(len(num)-1): for j in range(len(num)-i-1)...
2018-05-31 01:00:26
476
原创 最小生成树Kruskal算法—python实现
两种实现方法class DisjointSet(dict): '''不相交集''' def __init__(self, dict): pass def add(self, item): self[item] = item def find(self, item): if self[item] != item:...
2018-05-29 21:02:15
6725
9
原创 最小生成树prim算法—python实现
from collections import defaultdictfrom heapq import heapify, heappush, heappopdef Prim(nodes, edges): ''' 基于最小堆实现的Prim算法 ''' element = defaultdict(list) for start, stop, weight in e...
2018-05-29 20:58:52
3133
1
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人