2014
01-03

# 贪心算法

## 问题一、活动安排问题

/* 主题：活动安排问题
* 作者：chinazhangjie
* 邮箱：[email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */
* 开发语言：C++
* 开发环境：Vicrosoft Visual Studio
* 时间: 2010.11.21
*/

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std ;

struct ActivityTime
{
public:
ActivityTime (int nStart, int nEnd)
: m_nStart (nStart), m_nEnd (nEnd)
{ }
ActivityTime ()
: m_nStart (0), m_nEnd (0)
{ }
friend
bool operator < (const ActivityTime& lth, const ActivityTime& rth)
{
return lth.m_nEnd < lth.m_nEnd ;
}
public:
int m_nStart ;
int m_nEnd ;
} ;

class ActivityArrange
{
public:
ActivityArrange (const vector<ActivityTime>& vTimeList)
{
m_vTimeList = vTimeList ;
m_nCount = vTimeList.size () ;
m_bvSelectFlag.resize (m_nCount, false) ;
}
// 活动安排
void greedySelector ()
{
__sortTime () ;
// 第一个活动一定入内
m_bvSelectFlag[0] = true ;
int j = 0 ;
for (int i = 1; i < m_nCount ; ++ i) {
if (m_vTimeList[i].m_nStart > m_vTimeList[j].m_nEnd) {
m_bvSelectFlag[i] = true ;
j = i ;
}
}

copy (m_bvSelectFlag.begin(), m_bvSelectFlag.end() ,ostream_iterator<bool> (cout, ” “));
cout << endl ;
}

private:
// 按照活动结束时间非递减排序
void __sortTime ()
{
sort (m_vTimeList.begin(), m_vTimeList.end()) ;
for (vector<ActivityTime>::iterator ite = m_vTimeList.begin() ;
ite != m_vTimeList.end() ;
++ ite) {
cout << ite->m_nStart << “, “<< ite ->m_nEnd << endl ;
}
}

private:
vector<ActivityTime>    m_vTimeList ;    // 活动时间安排列表
vector<bool>            m_bvSelectFlag ;// 是否安排活动标志
int    m_nCount ;    // 总活动个数
} ;

int main()
{
vector<ActivityTime> vActiTimeList ;
vActiTimeList.push_back (ActivityTime(1, 4)) ;
vActiTimeList.push_back (ActivityTime(3, 5)) ;
vActiTimeList.push_back (ActivityTime(0, 6)) ;
vActiTimeList.push_back (ActivityTime(5, 7)) ;
vActiTimeList.push_back (ActivityTime(3, 8)) ;
vActiTimeList.push_back (ActivityTime(5, 9)) ;
vActiTimeList.push_back (ActivityTime(6, 10)) ;
vActiTimeList.push_back (ActivityTime(8, 11)) ;
vActiTimeList.push_back (ActivityTime(8, 12)) ;
vActiTimeList.push_back (ActivityTime(2, 13)) ;
vActiTimeList.push_back (ActivityTime(12, 14)) ;

ActivityArrange aa (vActiTimeList) ;
aa.greedySelector () ;
return 0 ;
}

## 贪心算法的基本要素

### 3、贪心算法与动态规划算法的差异

#### 背包问题：

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

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

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

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];

}

## 问题二、 哈夫曼编码

 a b c d e f 频率（千次） 45 13 12 16 9 5 定长码 000 001 010 011 100 101 变长码 0 101 100 111 1101 1100

3*(45+13+12+16+9+5) = 300 千位

1*45+3*13+3*12+3*16+4*9+4*5 ＝ 224 千位

### 1、前缀码

f(c)表示字符c出现的概率，dt(c)表示c的码长

### 2、构造哈夫曼编码

f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树。一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q。经过n1次的合并后，优先队列中只剩下一棵树，即所要求的树T

### 3、哈夫曼算法的正确性

(1)贪心选择性质

(2)最优子结构性质

<Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/>/* 主题: Haffman编码* 作者: chinazhangjie* 邮箱: [email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */* 开发环境 : 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 ;}

## 问题三、单源最大路径

### 1、算法基本思想

Dijkstra算法是解单源最短路径问题的贪心算法。

Dijkstra算法的迭代过程：

 迭代 s u dist[2] dist[3] dist[4] dist[5] 初始 {1} - 10 maxint 30 100 1 {1,2} 2 10 60 30 100 2 {1,2,4} 4 10 50 30 90 3 {1,2,4,3} 3 10 50 30 60 4 {1,2,4,3,5} 5 10 50 30 60

2、算法的正确性和计算复杂性

(1)贪心选择性质

(2)最优子结构性质

(3)计算复杂性

/* 主题: Dijkastra算法
* 作者: chinazhangjie
* 邮箱: [email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */
* 开发环境 : Microsoft Visual Studio 2008
* 时间 : 2010.11.23
*/
#include <iostream>
#include <vector>
#include <limits>
using namespace std ;

class BBShortestDijkstra
{
public:
BBShortestDijkstra (const vector<vector<int> >& vnGraph)
:m_cnMaxInt (numeric_limits<int>::max())
{
m_vnGraph = vnGraph ;
m_stCount = vnGraph.size () ;
m_vnDist.resize (m_stCount) ;
for (size_t i = 0; i < m_stCount; ++ i) {
m_vnDist[i].resize (m_stCount) ;
}
}

void doDijkatra ()
{
int nMinIndex = 0 ;
int nMinValue = m_cnMaxInt ;
vector<bool> vbFlag (m_stCount, false) ;
for (size_t i = 0; i < m_stCount; ++ i) {
m_vnDist[0][i] = m_vnGraph[0][i] ;
if (nMinValue > m_vnGraph[0][i]) {
nMinValue = m_vnGraph[0][i] ;
nMinIndex = i ;
}
}

vbFlag[0] = true ;
size_t k = 1 ;
while (k < m_stCount) {
vbFlag[nMinIndex] = true ;
for (size_t j = 0; j < m_stCount ; ++ j) {
// 没有被选择
if (!vbFlag[j] && m_vnGraph[nMinIndex][j] != m_cnMaxInt ) {
if (m_vnGraph[nMinIndex][j] + nMinValue
< m_vnDist[k-1][j]) {
m_vnDist[k][j] = m_vnGraph[nMinIndex][j] + nMinValue ;
}
else {
m_vnDist[k][j] = m_vnDist[k-1][j] ;
}
}
else {
m_vnDist[k][j] = m_vnDist[k-1][j] ;
}
}
nMinValue = m_cnMaxInt ;
for (size_t j = 0; j < m_stCount; ++ j) {
if (!vbFlag[j] && (nMinValue > m_vnDist[k][j])) {
nMinValue = m_vnDist[k][j] ;
nMinIndex = j ;
}
}
++ k ;
}

for (int i = 0; i < m_stCount; ++ i) {
for (int j = 0; j < m_stCount; ++ j) {
if (m_vnDist[i][j] == m_cnMaxInt) {
cout << "maxint " ;
}
else {
cout << m_vnDist[i][j] << " " ;
}
}
cout << endl ;
}
}
private:
vector<vector<int> >    m_vnGraph ;
vector<vector<int> >    m_vnDist ;
size_t m_stCount ;
const int m_cnMaxInt ;
} ;

int main()
{
const int cnCount = 5 ;
vector<vector<int> > vnGraph (cnCount) ;
for (int i = 0; i < cnCount; ++ i) {
vnGraph[i].resize (cnCount, numeric_limits<int>::max()) ;
}
vnGraph[0][1] = 10 ;
vnGraph[0][3] = 30 ;
vnGraph[0][4] = 100 ;
vnGraph[1][2] = 50 ;
vnGraph[2][4] = 10 ;
vnGraph[3][2] = 20 ;
vnGraph[3][4] = 60 ;

BBShortestDijkstra bbs (vnGraph) ;
bbs.doDijkatra () ;
}