0x06算法設計與分析複習（二）：算法設計政策-貪心法1

參考書籍：算法設計與分析——C++語言描述（第二版）

算法設計政策-貪心法

貪心法

• 貪心法是一種求解最優化問題的算法設計政策。
  • 貪心法是通過分步決策（stepwise decision）的方法來求解問題的。貪心法在求解問題的每一步上做出某種決策，産生n-元組解的一個分量。貪心法要求根據題意，標明一種最優量度标準（optimization criterion）或貪心準則（greedy criterion），也稱貪心選擇性質（greedy choice property）。這種量度标準通常隻考慮局部最優行。
• 在初始狀态下，解向量 solution=∅ ，其中不包含任何分量。使用最優量度标準，一次選擇一個分量，逐漸形成解向量 (x0,x1,⋯,xn−1) 。算法執行過程中生成的向量 (x0,x1,⋯,xk),k<n ，稱為部分解向量，也稱部分向量（partial vector）。
• 在根據最優量度标準選擇分量的過程中，還需要使用一個可行解判定函數。設 (x0,x1,⋯,xk−1) 是貪心算法已經生成的部分解，根據最優量度标準，算法目前選取解向量的第 k(k<n) 個分量為 xk ，此時需要使用可行解判定函數來判斷，在添加新的分量 xk 後所形成部分解 (x0,x1,⋯,xk) 是否違反可行解限制條件。
• 貪心法之是以被稱為是貪心的，是因為它希望每一步決策都是正确的，即要求在算法的每一步上，僅根據最有量度标準選擇分量，并隻需要保證形成的部分解不違反限制條件，最終得到n-元組不僅是可行解，而且必定是最優解。
• 事實上，最優量度标準一般并不從整體考慮，它隻是在某種意義上的局部最優選擇，每一步決策隻是在目前看來是最優的。是以，貪心法不能保證對所有問題都得到整體最優解。

//貪心法架構
SolutionType Greedy(SType a[], int n)
{
  //初始時，解向量不包含任何分量
  SolutionType solution=EmptySet;
  //多步決策，每次選擇解向量的一個分量
  for(int i = ; i<n;i++){
    //遵循最優量度标準選擇一個分量
    SType x= Select(a);
    //判定加入分量x後的部分解是否可行
    if(Feasible(solution, x))
      //形成新的部分解
      solution=Union(solution, x);
  }
  return solution;//傳回生成的最優解
}
           

對于一個貪心算法，必須進一步證明該算法的每一步上所做出的選擇，都必然最終導緻問題的一個整體最優解。

背包問題

問題描述

背包問題：已知一個載重為M的背包和n件物品，第i件物品的重量為 wi ，如果将第i件物品全部放進背包，将有收益 pi 這裡， wi>0,pi>0,0≤i<n 。所謂背包問題，是指求一種最佳裝載方案，使得收益最大。

• 0/1背包問題：每一件物品不能分割，隻能作為整體裝入背包，或者不能裝入。
• 一般背包問題：物品是可以分割的，允許将其中的一部分裝入背包。

用貪心法求解 0/1背包問題隻能求得近似解。

一般背包問題的貪心法求解

一般背包問題：

s.t.max∑i=0n−1pixi∑i=0n−1wixi≤Mwi>0pi>00≤xi≤10≤i<n

最優量度标準：選擇使 機關重量收益最大的物品裝入背包，即按 pi/wi 的非增次序選取物品。

基本步驟：

1. 首先計算每種物品機關重量的收益，并按非增次序進行排序；
2. 然後進行貪心選擇政策，選擇機關重量收益最高的物品裝入背包，依次政策一直進行下去，将盡可能多的物品全部裝入背包，直至背包裝滿；
3. 若裝入某件物品時，不能全部裝下，而背包内的物品總量仍未達到M，則根據背包的剩餘重量，選擇機關重量價值次高的物品盡可能多裝入背包。

//背包問題的貪心算法
template<class T>
  class Knapsack
  {
    public:
    //建立一個一維數組w和p，并賦初值
    Knapsack(int mSize, float cap, float *wei, T *prof);
    //數組x為背包問題的最優解
    void GreedyKnapsack(float* x);
    ...
      private:
    float m, *w;//m為背包載重量，w訓示存儲n個物品重量的數組
    T* p;//p訓示存儲n個物品收益的數組；
    int n;//n為物品數量
  };
template<class T>
  vois Knapsack<T>::GreedyKnapsack(float* x)
  {
    //前置條件：w[i]已按p[i]/w[i]的非增次序排列；
    float u = m;//u為背包剩餘載重量，初始時為m
    for(int i = ;i<n;i++)
      x[i]=;//對解向量初始化
    for(i = ;i<n;i++){
      //按最優量度标準選擇解的分量
      if(w[i]>u)
        break;
      x[i]=;
      u=u-w[i];
    }
    if(i<n)
      x[i]=u/w[i];
  }
           

定理：如果 p0/w0≥p1/w1≥⋯≥pn−1/wn−1 ，則以上程式求得的背包問題的解是最優解。

C語言實驗：設有載重 M=20 的背包，3件物品的重量為 (w0,w1,w2)=(18,15,10) ，物品裝入的收益為 (p0,p1,p2)=(25,24,15) 。

#include <stdio.h>
#include <stdlib.h>

void GreedyKnapsack(float p[], float w[], float x[], int n, float m);
void SortW(float* p, float* w, int n);
int main()
{
    float p[] = { ,, }, w[] = { ,, };
    float x[] = { ,, };
    float M = ;
    //對w[i]進行排序，按p[i]/w[i]的非增次序排列
    SortW(p, w, );
    printf("after sorting:\n");
    for (int i = ; i < ; i++) {
        printf("p[%d] = %f ", i, p[i]);
    }
    printf("\n");
    for (int i = ; i < ; i++) {
        printf("w[%d] = %f ", i, w[i]);
    }
    printf("\n");

    GreedyKnapsack(p, w, x, , M);

    printf("The solution is:\n");
    for (int i = ; i < ; i++) {
        printf("x[%d] = %f ", i, x[i]);
    }
    printf("\n");
    system("pause");
    return ;
}

void SortW(float* p, float* w, int n)
{
    int i = , j = n;
    float tmp = ;
    for (i = ; i < n; i++) {
        for (j = ; j < n - i-; j++) {
            if (p[j] / w[j] < p[j + ] / w[j + ]) {
                tmp = p[j];
                p[j] = p[j + ];
                p[j + ] = tmp;
                tmp = w[j];
                w[j] = w[j + ];
                w[j + ] = tmp;
            }
        }
    }
}

void GreedyKnapsack(float p[], float w[], float x[], int n, float m)
{
    //前置條件：w[i]已按p[i]/w[i]的非增次序排列；
    float u = m;//u為背包剩餘載重量，初始時為m
    int i = ;
    for (i = ; i<n; i++)
        x[i] = ;//對解向量初始化
    for (i = ; i<n; i++) {
        //按最優量度标準選擇解的分量
        if (w[i]>u)
            break;
        x[i] = ;
        u = u - w[i];
    }
    if (i<n)
        x[i] = u / w[i];
}
           

實驗結果：

after sorting:
p[] =  p[] =  p[] = 
w[] =  w[] =  w[] = 
The solution is:
x[] =  x[] =  x[] = 
請按任意鍵繼續. . .
           

貪心法的基本要素

一般來說，适用于貪心法求解的問題大都具有下面兩個特征：最優量度标準和最優子結構。

最優量度标準

最優量度标準（optimization criterion）或貪心準則（greedy criterion），也稱貪心選擇性質（greedy choice property）。是指所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動态規劃算法的主要差別。

所謂貪心法的最優量度标準，是指可以根據該量度标準，實行多步決策進行求解，雖然在該量度意義下所做的這些選擇都是局部最優的，但最終得到的解卻是全局最優的。選擇最優量度标準是使用貪心法求解問題的核心問題。值得注意的是，貪心算法每步做出的選擇可以依賴以前做出的選擇，但決不依賴将來的選擇，也不依賴于子問題的解。雖然貪心算法的每一步選擇也将問題簡化為一個規模更小的子問題，但由于貪心算法每一步選擇不依賴子問題的解，每步選擇隻按最優量度标準進行，是以，對于一個貪心算法，必須證明所采用的量度标準能夠導緻一個整體最優解。

貪心法的目前選擇可能會依賴于已經做出的選擇，但不依賴于尚未做出的選擇和子問題，是以它的特征是自頂向下，一步一步地做出貪心決策。

最優子結構

所謂最優子結構特征是 關于問題最優解的特征。當一個問題的最優解中包含了子問題的最優解時，則稱該問題具有最優子結構特性（optimal substructure）。一個可用貪心法求解的問題往往呈現最優子結構特性。

一般而言，如果一個最優化問題的解結構具有元組形式，并具有最優子結構特性，我們可以嘗試選擇量度标準。如果經過證明（一般是歸納法），确認該量度标準能夠導緻最優解，便可容易地按貪心法的算法架構設計出求解該問題的具體的貪心算法。問題的最優子結構性質是該問題可用動态規劃算法或貪心算法求解的關鍵特征。

并非所有的具有最優子結構特性的最優化問題，都能夠找到最優量度标準，此時，可以考慮采用動态規劃法來求解。

小結

一個問題能夠用貪心政策的條件是該問題的解是向量結構的，具有最優子結構特性，還要求能夠通過分析問題擷取最優量度标準。但是，按照該量度标準一次生成解的分量所形成的解是否确實是最優解仍需證明。

一個問題能夠使用貪心政策的條件如下：

• 問題的解是向量結構
• 具有最優子結構特性
• 能夠擷取最優量度标準
• 能證明是最優解