貪心算法
①在求最優解問題的過程中，依據某種貪心标準，從問題的初始狀态出發，直接去求每一步的最優解，通過若幹次的貪心選擇，最終得出整個問題的最優解，這種求解方法就是貪心算法。
②從貪心算法的定義可以看出，貪心算法不是從整體上考慮問題，它所做出的選擇隻是在某種意義上的局部最優解，而由問題自身的特性決定了該題運用貪心算法可以得到最優解。
③如果一個問題可以同時用幾種方法解決，貪心算法應該是最好的選擇之一。
貪心算法的性質：
貪心選擇性質是指所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到。
i.這是貪心算法可行的第一個基本要素，也是貪心算法與動态規劃算法的主要差別。
（1）在動态規劃算法中，每步所做的選擇往往依賴于相關子問題的解，因而隻有在解出相關子問題後，才能做出選擇。
（2）在貪心算法中，僅在目前狀态下做出最好選擇，即局部最優選擇，然後再去解出這個選擇後産生的相應的子問題。
最優子結構性質：
①當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構性質。
i.運用貪心政策在每一次轉化時都取得了最優解。問題的最優子結構性質是該問題可用貪心算法或動态規劃算法求解的關鍵特征。
②貪心算法的每一次操作都對結果産生直接影響，而動态規劃則不是。
i.貪心算法對每個子問題的解決方案都做出選擇，不能回退；動态規劃則會根據以前的選擇結果對目前進行選擇，有回退功能。
ii.動态規劃主要運用于二維或三維問題，而貪心一般是一維問題。
貪心算法的求解過程：
使用貪心算法求解問題應該考慮如下幾個方面：
（1）候選集合A：為了構造問題的解決方案，有一個候選集合A作為問題的可能解，即問題的最終解均取自于候選集合A。
（2）解集合S：随着貪心選擇的進行，解集合S不斷擴充，直到構成滿足問題的完整解。
（3）解決函數solution：檢查解集合S是否構成問題的完整解。
（4）選擇函數select：即貪心政策，這是貪心法的關鍵，它指出哪個候選對象最有希望構成問題的解，選擇函數通常和目标函數有關。
（5）可行函數feasible：檢查解集合中加入一個候選對象是否可行，即解集合擴充後是否滿足限制條件。
貪心算法的一般流程：
//A是問題的輸入集合即候選集合
Greedy(A)
{
S={ }; //初始解集合為空集
while (not solution(S)) //集合S沒有構成問題的一個解
{
x = select(A); //在候選集合A中做貪心選擇
if feasible(S, x) //判斷集合S中加入x後的解是否可行
S = S+{x};
A = A-{x};
}
return S;
｝
活動安排問題
活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合，是可以用貪心算法有效求解的很好例子。
該問題要求高效地安排一系列争用某一公共資源的活動。
貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動能相容地使用公共資源
問題描述：
①設有n個活動的集合E＝{1，2，…，n}，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間内隻有一個活動能使用這一資源。
②每個活動i都有一個要求使用該資源的起始時間si和一個結束時間fi，且si＜fi。如果選擇了活動i，則它在半開時間區間[si ，fi )内占用資源。若區間[si ，fi )與區間[sj，fj )不相交，則稱活動i與活動j是相容的。當 si ≥ fj 或 sj ≥ fi 時，活動i與活動j相容。
③活動安排問題就是在所給的活動集合中選出最大的相容活動子集合。
//資料結構
struct action{
int s; //起始時間
int f; //結束時間
int index; //活動的編号
};
//活動的集合E記為數組：
action a[1000];
按活動的結束時間升序排序
排序比較因子：
bool cmp(const action &a, const action &b)
{
if (a.f<=b.f) return true;
return false;
}
使用标準模闆庫函數排序（下标0未用）：
sort(a, a+n+1, cmp);
算法：
//形參數組b用來記錄被選中的活動
void GreedySelector(int n, action a[], bool b[])
{
b[1] = true; //第1個活動是必選的
//記錄最近一次加入到集合b中的活動
int preEnd = 1;
for(int i=2; i<=n; i++)
if (a[i].s>=a[preEnd].f)
{
b[i] = true;
preEnd = i;
}
}
背包問題
1.給定一個載重量為M的背包，考慮n個物品，其中第i個物品的重量 ，價值wi （1≤i≤n），要求把物品裝滿背包，且使背包内的物品價值最大。
2.有兩類背包問題（根據物品是否可以分割），如果物品不可以分割，稱為0—1背包問題（動态規劃）；如果物品可以分割，則稱為背包問題（貪心算法）。
資料結構
struct bag{
int w; //物品的重量
int v; //物品的價值
double c; //成本效益
}a[1001]; //存放物品的數組
排序因子（按成本效益降序）：
bool cmp(bag a, bag b){
return a.c >= b.c;
}
使用标準模闆庫函數排序（最好使用stable_sort()函數，在成本效益相同時保持輸入的順序）：
sort(a, a+n, cmp);
計算背包問題的貪心算法
//形參n是物品的數量，c是背包的容量M，數組a是按物品的成本效益降序排序
double knapsack(int n, bag a[], double c)
{
double cleft = c; //背包的剩餘容量
int i = 0;
double b = 0; //獲得的價值
//當背包還能完全裝入物品i
while(i<n && a[i].w<cleft)
{
cleft -= a[i].w;
b += a[i].v;
i++;
}
//裝滿背包的剩餘空間
if (i<n) b += 1.0*a[i].v*cleft/a[i].w;
return b;
}
如果要獲得解向量 X={x1, x2…xn}，則需要在資料結構中加入物品編号：
如果要獲得解向量 ，則需要在資料結構中加入物品編号：
struct bag{
int w;
int v;
double x; //裝入背包的量，0≤x≤1
int index; //物品編号
double c;
}a[1001];
計算背包問題的貪心算法，同時得到解向量
double knapsack(int n, bag a[], double c)
{
double cleft = c;
int i = 0;
double b = 0;
while(i<n && a[i].w<=cleft)
{
cleft -= a[i].w;
b += a[i].v;
//物品原先的序号是a[i].index，全部裝入背包
a[a[i].index].x = 1.0;
i++;
}
if (i<n) {
a[a[i].index].x = 1.0*cleft/a[i].w;
b += a[a[i].index].x*a[i].v;
}
return b;
}