貪心方法

1.背包問題

按效益值/重量 進行排序輸入

2.帶限期的作用排序

按效益值進行排序輸入

3 最小生成樹：

?貪心方法：每次計入成本最小的邊?

原樹T， 欲構造的最小生成樹T'

Prim： 從T中選與T'中結點相連的成本最小的邊。 且：邊之前不在T'中。加入Tp后不會構成環

Kruskal: 從T中成本最小的邊。 ? ? ?且：邊之前不在T'中。加入Tp后不會構成環

從中可以看出：Prim在構造過程中，T'始終是一棵樹。

? ? ? ? ? ? ? ? ? ? Kruaskal在構造過程，T'可能是一個森林，結果時是一棵樹。

4 單源點最短路徑

Dijskstra:

? Dist(w)= min { ?Dist(w), Dist(u)+cost(u,w) }

按prim法選擇一個結點u,加入集合S;?

? ?對每一個u所連接的結點w，更新源點到w的最短距離：若 源點到u的最短距離+u到w成本 <源點到w最短距離，則更新。

?