# 貪婪演算法
貪婪演算法就是做眼前最佳的動作，也就是局部解，但是到最後不見得是最好的動作，以下舉一個找零錢的例子。
通常找顧客零錢都是先將面額大的給顧客，再將較第二大的面額給顧客，依序這樣下去，直到不能找為止，所以貪婪演算法就是運用這個想法。

#include <iostream>
using namespace std;

int main(){
    int cash[10],n;
    cash[0] = 1;
    cash[1] = 5;
    cash[2] = 10;
    cash[3] = 50;
    cash[4] = 100;
    cash[5] = 500;
    cash[6] = 1000;
    cin >> n;
    cout << n << "=";
    for(int i = 6;i >= 0;i--){
        if(n >= cash[i]){
            cout << cash[i] << "*" << n/cash[i] << " ";
            n = n%cash[i];
        }
    }

    return 0;
}

## 貪婪演算法-最小生成樹(Minimum spanning trees)MST
其實tree是一種資料結構，但我配合greedy來講。
Tree的特性，必連通，但不能有cycle。
MST的定義就是生成出來的樹，他的邊的總和最小的。
英文版定義（由於翻譯成中文可能無法清楚表達他的含義，所以這邊使用別人的定義，原文是英文）：
Definition:
G = (V,E):weighted connected undirected graph
* <span style = "color:blue">Spanning tree</span> : S = (V,T),T ⊆ E,undirected tree
* <span style = "color:blue">Minimum spanning tree(MST)</span> : a spanning tree with the smallest total weight.
中文定義：
1. 樹(tree):一個無向連通非環狀圖(acyclic,connected, undirected graph)
2. 有根樹(rooted tree):以某個頂點為跟的樹（獨立於樹之外的頂點不能作為根）。因此有根樹也被直接稱為樹。
3. 生成樹(spanning tree):包含圖中所有頂點且符合樹的定義的連通子圖。
4. 最小生成樹(minimum spanning tree):即具有最小的權重的生成樹。
## 用貪婪演算法解最小生成樹

F = empty set
while(當問題未得解){
	找出問題區域最佳解的方式找出一個邊;
	if(選出來的邊不會使F產生任何cycle)
		將邊加入F中;
	if(答案是生成樹)
		此問題得解;
}

## Kruskal algorithm
先將所有邊拿掉，接著再依序找小邊，並隨時確保他不會形成一個cycle。
## Prim algorithm
先挑一個點，然後找那個頂點連接的邊哪個最小，然後當所有的點都選到後就結束了。