大漠落日

while(!dead) study++;
posts - 46, comments - 126, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

贪心算法

Posted on 2011-06-24 14:25 乱78糟 阅读(429) 评论(0)  编辑 收藏 引用 所属分类: 算法&数据结构

活动选择问题:

设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下,:

i

1

2

3

4

5

6

7

8

9

10

11

s[i]

1

3

0

5

3

5

6

8

8

2

12

f[i]

4

5

6

7

8

9

10

11

12

13

14

求最多一次性不重复安排几次活动(s[i]表示活动起始时间,f[i]表示结束时间)

/***********************************
*    贪心算法之活动选择问题
*    yanzh 2011-6-24
***********************************
*/
#include 
<iostream>
using namespace std;

#define SET        1
#define UNSET    0

#define COUNT    12

typedef 
struct Activity{
    
int    start;    //活动起始时间
    int end;    //活动终止时间
    int set;    //活动是否被安排,0不安排, 1安排

    Activity
& operator=(const Activity &act)
    {
        
if (this != &act)
        {
            
this->start = act.start;
            
this->end = act.end;
            
this->set = act.set;
        }
        
return *this;
    }
}ACT;

//带安排的活动,按照结束时间递增顺序已经排好序(算法导论16.1章)
//结果有两个最大集合,下标分别为:{1,4,8,11}和{2,4,9,11}
//act[0]占位用,不具有实际意义
ACT act[COUNT] = { {0,0,0}, {1,4,0}, {3,5,0}, {0,6,0}, {5,7,0}, {3,8,0}, {5,9,0}, 
                    {
6,10,0}, {8,11,0}, {8,12,0}, {2,13,0}, {12,14,0} };

void output_result()
{
    
int total = 0;

    
for (int i = 0; i < COUNT; i++)
    {
        
if (act[i].set == SET)
        {
            cout
<<"第 "<<i<<" 个活动被安排"<<endl;
            total
++;
        }
    }

    cout
<<"总计有 "<<total<<" 个活动被安排"<<endl;
}

//递归求
//参数: i,j表示带处理的子问题S(i,j)
void recursion_activity(int i, int j)
{
    
int m = i + 1;
    
    
//找到S(i,j)中的第一个活动
    while (m < j && act[m].start < act[i].end)
    {
        m 
= m + 1;
    }

    
if (m < j)
    {
        act[m].
set = SET;
        
return recursion_activity(m, j);
    }
}

//迭代求
void iteration_activity()
{
    
int i = 0;

    
for (int m = 1; m < COUNT; m++)
    {
        
if (act[m].start >= act[i].end)
        {
            act[m].
set = SET;
            i 
= m;
        }
    }
}

/*******************************************************************************
*                                定理16.1
*    对于任意非空子问题S(i,j), 设a(m)是S(i,j)中具有最早结束时间的活动:那么,
*        1)活动a(m)在S(i,j)的某最大兼容活动子集中被使用;
*        2)子问题s(i,m)为空,所以选择a(m)将使子问题S(m,j)为唯一可能非空的子问题。
******************************************************************************
*/
int main(int argc, char *argv[])
{
    
//有参数用递归,否则用迭代
    if (argc > 1)
        recursion_activity(
0, COUNT);
    
else
        iteration_activity();
    
    output_result();

    
return 0;    
}


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理