最优化问题 #
1.最优化问题通常包括两部分
目标函数：需要最大化或最小化的值。eg：两地飞机票价
约束条件集合（可以为空）：必须满足的条件集合。eg：旅行时间的上界
背包问题 #
1.贪婪算法：对于背包问题，找出近似解的最简单方法就是贪婪算法，首先选择最好的物品，然后是次好的，继续下去，知道背包装满。
贪婪算法在每一步都作出当时看起来最佳选择，也就是说，他总是做出局部最优的选择，寄希望这样的选择能导致全局最优解。
动态规划 #
1.动态规划算法通常用于求解某种最优性质的问题，在这类问题中，可能会有很多可行解，没一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治算法类似，其基本思想也是讲待求解问题分解为若干子问题，先求解子问题，然后从子问题的解得到原问题的解，与分治法不同的是，适用于动态规划算法求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数据太多，有些子问题被重复计算很多次，如果我们保存了子问题的答案，而在需要时找出已解决子问题的答案，不管该子以后是否用到，只要它被计算过，就将其结果填入表中。这就是动态规划算法的基本思路。具体的动态规划算法多种多样，但他们具有相同的填表格式。
图 #
图是由便连接起来的节点对象的集合，边也可称为弧，节点也可称为顶点，如果边是单向的，则图称为有向图，在有向图中，从节点n1到n2有一条边，我们就称n1为源节点或父节点，n2为目标节点或子节点。
1.广度优先搜索：
给定图G = (V,E)和一个可以识别的源节点s，广度优先搜索对图G中的边进行系统性的探索来发现可以从源节点s到达的所有节点。该算法能够计算从源节点s到每个可到达的结点的距离（最少的边数），同时生成一颗“广度优先搜索树”。该树以源节点s为根节点，包括所有可以从s到达的结点。对于每个从源节点s可以到节点v，在广度优先搜素树里从节点s到节点v的简单路径所对应的就是图G中从节点s到节点v的“最短路径”，即包含最少边数的路径。该算法可用于有向图和无向图。
代码:BFS（G，s）
1 for each vertex u in G.V-{s}
2 u.color = WHITE
3 u.d = 无穷大
4 u.p = NIL
5 s.color = GRAY
6 s.d = 0
7 s.p = NUL
8 Q = NULL
9 ENQUEUE(Q,s)
10 while(Q != NULL)
11 u = DEQUEUE(Q)
12 for each v in G.Adj[u]
13 if v.color == WHITE
14 v.color = GRAY
15 v.d = u.d + 1
16 v.p = u
17 ENQUEUE(Q,v)
18 u.color = BLACK
2.深度优先搜索
深度优先搜索总是对最近才发现的结点v的出发边进行探索，直到该节点的所有出发边都被发现为止，一旦结点v的所有出发边都被发现，搜索则回溯到v的前驱结点（v是经过该结点才被发现的），来搜索该前驱结点的出发边。该过程一直持续到从源结点可以达到的所有结点都被发现为止。如果还存在尚未发现的结点，则深度优先搜索从这些未被发现的结点中任选一个作为新的源结点，并重复同样的搜索过程。
代码：DFS(G)
1 for each vertex u in G.V
2 u.color = WHITE
3 u.p = NIL
4 time = 0
5 for each vertex u in G.V
6 if u.color == WHITE
7 DFS_VISIT(G,u)
DFS_VISIT(G,u)
1 time = time + 1
2 u.d = time
3 d.color = GRAY
4 for each v in G:Adj[u]
5 if v.color == WHITE
6 v.p = u
7 DFS-VISIT(G,v)
8 u.color = BLACK
9 time = time + 1
10 u.f = time