五大常用算法之贪心算法

Love The Way You Lie 2022-08-24 06:06 143阅读 0赞

看了 [五大常用算法之一][Link 1] 这篇博文，感觉理解了很多，可是纯粹都是理论，缺少一些示例，所以准备综合一篇博文，以帮助自己记忆，原文：

[http://www.cnblogs.com/steven\_oyj/archive/2010/05/22/1741375.html][Link 1]

**一、基本概念：**

所谓贪心算法是指，在对问题求解时，总是做出在 当前看来是最好的选择 。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的 局部最优解 。

贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。

所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。

**二、贪心算法的基本思路：**

1.建立数学模型来描述问题。

2.把求解的问题分成若干个子问题。

3.对每一子问题求解，得到子问题的局部最优解。

4.把子问题的解局部最优解合成原来解问题的一个解。

**三、贪心算法适用的问题**

**      贪心策略适用的前提是：局部最优策略能导致产生全局最优解。**

**    实际上，贪心算法适用的情况很少。一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断。**

**四、贪心算法的实现框架**

从问题的某一初始解出发；

while （能朝给定总目标前进一步）

利用可行的决策，求出可行解的一个解元素；

由所有解元素组合成问题的一个可行解；

#### 五、示例 ####

#### （1）背包问题： ####

与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1 <= i <= n。

这2类问题都具有最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。

### 用贪心算法解背包问题的基本步骤： ###

首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。

伪代码：

void Knapsack(int n,float M,float v\[\],float w\[\],float x\[\])

Sort(n,v,w);

int i;

for (i = 1 ; i <= n ; i++)

x\[i\] = 0;

float c=M;

for (i=1;i<=n;i++) \{

if (w\[i\] > c) break;

x\[i\]=1;

c-=w\[i\];

if (i <= n)

x\[i\]=c / w\[i\];

算法knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为 O（nlogn）。

为了证明算法的正确性，还必须证明背包问题具有贪心选择性质。

对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。实际上也是如此，动态规划算法的确可以有效地解0-1背包问题。

（2） 哈夫曼算法

代码

/* 主题: Haffman编码
    * 作者: chinazhangjie
    * 邮箱: chinajiezhang@gmail.com
    * 开发环境 : Microsoft Visual Studio 2008
    * 时间 : 2010.11.21
    */
    
    
    #include <iostream>
    #include <vector>
    #include <queue> 
    using namespace std ;
    
    
    
    
    class HaffmanNode
    {
    public:
        HaffmanNode (int nKeyValue, 
                    HaffmanNode* pLeft = NULL,
                    HaffmanNode* pRight = NULL)
        { 
            m_nKeyValue = nKeyValue ;
            m_pLeft = pLeft ;
            m_pRight = pRight ;
        }
    
    
        friend 
        bool operator < (const HaffmanNode& lth, const HaffmanNode& rth)
        {
            return lth.m_nKeyValue < rth.m_nKeyValue ;
        }
    
    
    public:
        int        m_nKeyValue ;    
        HaffmanNode*    m_pLeft ;
        HaffmanNode*    m_pRight ;
    } ;
    
    
    class HaffmanCoding
    {
    public:
        typedef priority_queue<HaffmanNode*> MinHeap ;
        typedef HaffmanNode*    HaffmanTree ;
    
    
    public:
        HaffmanCoding (const vector<int>& weight) 
            : m_pTree(NULL)
        {
            m_stCount = weight.size () ;
            for (size_t i = 0; i < weight.size() ; ++ i) {
                m_minheap.push (new HaffmanNode(weight[i], NULL, NULL)) ;
            }
        }
        ~ HaffmanCoding()
        {
            __destroy (m_pTree) ;
        }
    
    
        // 按照左1右0编码 
        void doHaffmanCoding ()
        {
            vector<int> vnCode(m_stCount-1) ;
            __constructTree () ;
            __traverse (m_pTree, 0, vnCode) ;
        }
        
    private:
        void __destroy(HaffmanTree& ht) 
        {
            if (ht->m_pLeft != NULL) {
                __destroy (ht->m_pLeft) ;
            }
            if (ht->m_pRight != NULL) {
                __destroy (ht->m_pRight) ;
            }
            if (ht->m_pLeft == NULL && ht->m_pRight == NULL) {
                // cout << "delete" << endl ;
                delete ht ;
                ht = NULL ;
            }
        }
        void __traverse (HaffmanTree ht,int layers, vector<int>& vnCode) 
        {
            if (ht->m_pLeft != NULL) {
                vnCode[layers] = 1 ;
                __traverse (ht->m_pLeft, ++ layers, vnCode) ;
                -- layers ;
            }
            if (ht->m_pRight != NULL) {
                vnCode[layers] = 0 ;
                __traverse (ht->m_pRight, ++ layers, vnCode) ;
                -- layers ;
            }
            if (ht->m_pLeft == NULL && ht->m_pRight == NULL) {
                cout << ht->m_nKeyValue << " coding:  " ;
                for (int i = 0; i < layers; ++ i) {
                     cout << vnCode[i] << " " ;
                }
                cout << endl ;
            }
        }
    
    
        void __constructTree ()
        {
            size_t i = 1 ;
            while (i < m_stCount) {
                HaffmanNode* lchild = m_minheap.top () ;
                m_minheap.pop () ;
                HaffmanNode* rchild = m_minheap.top () ;
                m_minheap.pop () ;
                
                // 确保左子树的键值大于有子树的键值
                if (lchild->m_nKeyValue < rchild->m_nKeyValue) {
                    HaffmanNode* temp = lchild ;
                    lchild = rchild ;
                    rchild = temp ;
                }
                // 构造新结点
                HaffmanNode* pNewNode = 
                    new HaffmanNode (lchild->m_nKeyValue + rchild->m_nKeyValue,
                    lchild, rchild ) ;
                m_minheap.push (pNewNode) ;
                ++ i ;
            }
            m_pTree = m_minheap.top () ;
            m_minheap.pop () ;
        }
    
    
    private:
        vector<int> m_vnWeight ;    // 权值
        HaffmanTree m_pTree ;
        MinHeap        m_minheap ;
        size_t        m_stCount ;        // 叶结点个数
    } ;
    
    
    
    
    int main()
    {    
        vector<int> vnWeight ;
        vnWeight.push_back (45) ;
        vnWeight.push_back (13) ;
        vnWeight.push_back (12) ;
        vnWeight.push_back (16) ;
        vnWeight.push_back (9) ;
        vnWeight.push_back (5) ;
    
    
        HaffmanCoding hc (vnWeight) ;
        hc.doHaffmanCoding () ;
        return 0 ;
    }

[Link 1]: http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741370.html