算法概论实验八 贪心法

算法概论实验

实验八
实验目的与要求：
（1） 掌握贪心法的基本思想和设计方法。
1．区间调度问题
【问题描述】
给定n个活动，其中的每个活动ai包含一个起始时间si与结束时间fi。设计与实现算法从n个活动中找出一个最大的相互兼容的活动子集S。
要求：分别设计动态规划与贪心算法求解该问题。其中，对贪心算法分别给出递归与迭代两个版本的实现。

贪心法迭代

#include "stdafx.h"
#include <iostream>
using namespace std;
int GetSet(int *si, int *fi, int n)
{
    //创建一个记录数组，用于最后判定是否选取
    bool *result=new bool[n];
    memset(result, false, sizeof(result));
    result[0] = true;//初始设定
    int selected_index = 0;//第一个选中的
    for (int i = 1; i < n;i++)
    {
        if (fi[selected_index] <= si[i])//这种情况下是能够兼容的
        {
            result[i] = true;
            selected_index = i;
        }
    }
    //输出
    int nct = 0;
    cout << "最大兼容子集为：";
    for (int i = 0; i < n;i++)
    {
        if (result[i]==true)
        {
            cout << i + 1 << "\t";
            nct++;
        }
    }
    return nct;
}
int main()
{
    int si[] = {1,3,0,5,3,5,6,8,8,2,12};
    int fi[] = {4,5,6,7,8,9,10,11,12,13,14};
    int n = 11;
    cout << endl<<"省去排序过程,最兼容活动子集的数目为："<< GetSet(si, fi, n);
    return 0;
}

贪心法 递归

每次递归，将问题的规模减少1~n，

#include "stdafx.h"
#include <iostream>
using namespace std;
//i是上一个符合条件的id，为了完整性，在第一列加上-1，n是总数目
void GetSet(int *si, int *fi, int i, int n)
{
    int m = i + 1;
    while (m <= n && si[m] < fi[i])//找第一个符合的
        m = m + 1;
    if (m <= n)
    {
        cout << m << "\t";
        GetSet(si, fi, m, n);
    }
}
int main()
{
    int si[] = { -1,1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12 };
    int fi[] = { -1,4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 };
    int n = 11;
    GetSet(si, fi, 0, 11);
}

动态规划

#include<iostream>
using namespace std;
//动态规划实现
int GetSet(int *start, int *finish, int n)
{
    //c[i][j]表示第i个工作结束后到第j个工作开始前之间存在的可兼容的工作个数
    //new c[i][j]
    int **c = new int *[n];
    for(int i=0; i<n; i++)
        c[i] = new int[n];
    //c[i][j]初始赋值
    for(i=0; i<n; i++)
        for(int j=0; j<n; j++)
            c[i][j] = 0;
    for(int j=0; j<n; j++)
    {
        for(i=0; i<n; i++)
        {
            if(i<j)
            {
                int s = finish[i];
                int f = start[j];
                for(int k=i+1; k<j; k++)
                    if(start[k]>=s && finish[k]<=f)
                    {
                        if(c[i][j]<(c[i][k]+c[k][j]+1))
                            c[i][j] = c[i][k]+c[k][j]+1; //分解成更小子问题
                    }                       
            }
        }           
    }
    return c[0][n-1];   //最终目标
}
int main()
{
    //已经按完成时间排好序
    int start[] = {-1,3,0,5,3,5,6,8,8,2,1000};
    int finish[] = {0,5,6,7,8,9,10,11,12,13,10000};
    int n = 11; //活动只有9个
    cout<<"最大兼容活动子集的大小为："<<GetSet(start, finish, n)<<endl;
    return 0;
}