會場安排問題貪心算法

問題描述：

假設要在足夠多的會場裡安排一批活動，并希望使用盡可能少的會場。設計一個有效的貪心算法進行安排（這個問題實際上是著名的圖着色問題。若将每一個活動作為圖的一個頂點，不相容活動間用邊相連。使相鄰頂點着有不同顔色的最小着色數，相應于要找的最小會場數）。

問題解答：

<1>、用貪心選擇政策解會場安排問題。

貪心算法重要的兩個性質：貪心選擇性質和最優子結構性質。

1、 問題的貪心選擇性質

證明：首先将會場安排問題數學化，設有n個活動的集合 e= { 1 ，2 ，…，n }，每個活動 i 都有一個要求使用該會場的起始時問si 和一個結束時問fi 。即k是所需最少會場的個數。設活動已排序，( a1 , a2 , … ,ak )是所需要的k個已安排了活動的會場。①當k = 1時，也就是所有的活動在一個會場裡相容，a1 是滿足貪心選擇性質的最優解；②當k>= 2時，取b1=a1,bk=ak (即bk是安排了m個活動的一個會場，(n-m)個活動都安排在b1 到bk-1個會場裡)。就是（n-m）個活動安排需要（k -1）個會場。則(b1,b2 ,…,bk-1 )是（n - m）個活動可行解。另一方面，由{( a1 ,a2,…,ak)-ak}=(b1,b2,…,bk-1)知，(b1,b2,…,bk-1)也是滿足貪心選擇性質的最優解，是以，會場安排問題具有貪心選擇性質。

2、 問題的最優子結構性質

證明：( a1,a2, …,ak )是n個活動的集合e= {1，2 ，…，n }所需會場的最優解。設a1中安排了m個相容的活動，那麼也就是說（n-m）個活動完全安排需要k-1個會場。假設（n - m）個活動安排隻需要k-2個會場或則更少的會場。也就是說n個活動安排隻需要k-1個會場或者更少的會場就可以安排完，則前後出現沖突。一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構性質。

<2>、算法實作思路：

1）、首先定義一個時間類Node，有兩個data，flag屬性，其中data是時間值，flag是判斷活動開始還是結束。

2）、對所有的時間對象按.data排序到一個數組中，其中選擇歸并排序方法進行排序。

3）、該算法的貪心選擇的意義是使剩餘的可安排時間段極大化，以便安排盡可能多的相容活動。依次取出該數組的資料，判斷其屬性flag，若是一個開始時間，則Count++，若是結束時間Count--，其中最大的Count值就是要求的最少的會場數。

<3>、算法程式：

#include<iostream>
#include<fstream>
using namespace std;

//活動的時間類
class Node
{
public:
    int data;//時間值
    bool flag;//判斷是開始還是結束，0表示開始，1表示結束
    bool operator<(Node &secondRational);//按時間值比較兩個對象的大小
};

//比較類中時間值的大小
bool Node::operator<(Node &secondRational)
{
    if((this->data-secondRational.data)<0)
        return true;
    else
        return false;
}

//複制數組函數
template<typename T>
void arraycopy(T source[],int sourceStartIndex,T target[],int targetStartIndex,int length);
//合并數組函數
template<typename T>
void merge(T list1[],int list1Size,T list2[],int list2Size,T temp[]);
//歸并排序函數
template<typename T>
void mergeSort(T list[],int arraySize)
{
    if(arraySize>1)
    {
        //複制排序前半部分數組
        T *firstHalf=new T[arraySize/2];
        arraycopy(list,0,firstHalf,0,arraySize/2);
        mergeSort(firstHalf,arraySize/2);

        //複制排序後半部分數組
        int secondHalfLength=arraySize-arraySize/2;
        T *secondHalf=new T[secondHalfLength];
        arraycopy(list,arraySize/2,secondHalf,0,secondHalfLength);
        mergeSort(secondHalf,secondHalfLength);

        //合并複制兩部分數組
        T *temp=new T[arraySize];
        merge(firstHalf,arraySize/2,secondHalf,secondHalfLength,temp);
        arraycopy(temp,0,list,0,arraySize);

        delete []temp;
        delete []firstHalf;
        delete []secondHalf;
    }
}

//将兩個數組按大小順序合并入一個數組中
template<typename T>
void merge(T list1[],int list1Size,T list2[],int list2Size,T temp[])
{
    int current1=0;
    int current2=0;
    int current3=0;

    while(current1<list1Size&¤t2<list2Size)
    {
        if(list1[current1]<list2[current2])
            temp[current3++]=list1[current1++];
        else
            temp[current3++]=list2[current2++];
    }

    while(current1<list1Size)
        temp[current3++]=list1[current1++];
    while(current2<list2Size)
        temp[current3++]=list2[current2++];
}

//将一個數組複制到另一個數組中
template<typename T>
void arraycopy(T source[],int sourceStartIndex,T target[],int targetStartIndex,int length)
{
    for(int i=0;i<length;i++)
    {
        target[i+targetStartIndex]=source[i+sourceStartIndex];
    }
}

//最少會場數函數
int Greedyplan(Node f[],int n)
{
    int Count=0;
    int maxCount=0;
    /*
    周遊活動時間，若此時間為開始時間，則Count+1,為結束時間，則Count-1
    統計得出最大的Count值，并将Count值賦給maxCount，
    此maxCount值就為最少的會場數
    */
    for(int i=0;i<n;i++)
    {
        if(f[i].flag==0)//若此時間為開始時間Count+1
        {
            Count++;
            if(Count>maxCount)//記錄次循環中最大的Count值
            {
                maxCount=Count;
            }
        }
        else//若為結束時間Count-1
        {
            Count--;
        }
    }
    return maxCount;
}

int main()
{
    //讀出輸入檔案中的資料
    fstream fin;
    fin.open("input.txt",ios::in);
    if(fin.fail())
    {
        cout<<"File does not exist!"<<endl;
        cout<<"Exit program"<<endl;
        return 0;
    }

    int n;
    fin>>n;

    //建立兩個Node類型的數組，用于存放開始時間和結束時間
    Node *a=new Node[n];
    Node *b=new Node[n];
    for(int i=0;i<n;i++)
    {
        fin>>a[i].data;
        fin>>b[i].data;
    }

    //将開始時間表示為0
    for(int j=0;j<n;j++)
    {
        a[j].flag=0;    
    }
    //将結束時間表示為1
    for(int k=0;k<n;k++)
    {
        b[k].flag=1;    
    }

    //再建立一個Node類型的數組，将前兩個數組中的資料複制到此數組中
    Node *c=new Node[2*n];
    arraycopy(a,0,c,0,n);
    arraycopy(b,0,c,n,n);

    //将數組c按時間值大小排序，此排序為穩定的歸并排序
    mergeSort(c,2*n);

    //調用最少會場數函數
    int mm=Greedyplan(c,2*n);
    //控制台輸出
    cout<<"最少會場數為："<<mm<<endl;

    //将結果資料寫入到輸出檔案
    fstream fout;
    fout.open("output.txt",ios::out);
    fout<<mm;

    fin.close();
    fout.close();
    system("pause");
    return 0;
}