week13

背包问题的理解

背包问题：物品有两个属性：重量和价值，即一个是增益，一个是获取限制，求利益最大化
贪婪算法：
1、优先选择价值高
2、优先选择重量低
3、优先选择 价值/重量 大

最优解：
盗贼背包问题被称为0/1背包问题
贪婪算法近似解复杂度 O（nlog(n)）
暴力最优解复杂度O（n**n）

图最优化问题的理解

图：边连接起来的节点对象的集合
源节点=父节点
目标节点=子节点

欧拉定理:
如果想一次性遍历每座桥且每座桥只走一次，那么必须满足：
行走过程中间的每个节点（也就是行走过程中既走入又走出的岛屿，不包括起点和终点）必须被
偶数条边相连

如何选择图类的数据结构
1、n x n邻接矩阵
2、邻接表

DFS函数实现的算法是递归形式的深度优先搜索算法

动态规划问题的理解

适用于解决具有重复子问题和最优子结构的问题
递归斐波那契效率问题
复杂度O(fib(n))

动态规划问题的核心：保存调用结果，需要的时候查找，成为备忘录法
备忘录法斐波那契数列：

def fastFib(n, memo = {}):
"""假设n是非负整数， memo只进行递归调用 返回第n个斐波那契数"""
if n == 0 or n == 1:
return 1
try:
return memo[n]
except KeyError:
result = fastFib(n-1, memo) + fastFib(n-2, memo)
memo[n] = result
return result