采取C++完成區間圖著色成績（貪婪算法）實例詳解

采取C++完成區間圖著色成績（貪婪算法）實例詳解。本站提示廣大學習愛好者：（采取C++完成區間圖著色成績（貪婪算法）實例詳解）文章只能為提供參考，不一定能成為您想要的結果。以下是采取C++完成區間圖著色成績（貪婪算法）實例詳解正文

本文所述算法即假定要用許多個教室對一組運動停止調劑。我們願望應用盡量少的教室來調劑一切運動。采取C++的貪婪算法，來肯定哪個運動應用哪一間教室。

關於這個成績也常被稱為區間圖著色成績，即相容的運動著同色，不相容的著分歧色彩，使得所用色彩數起碼。

詳細完成代碼以下：

//貪婪算法

#include "stdafx.h"
#include<iostream>
#define N 100
using namespace std;

struct Activity
{
 int number; //運動編號
 int begin; //運動開端時光
 int end; //運動停止時光
 bool flag;//此運動能否被選擇
 int roomNum; //此運動在哪間教室舉辦
};
//關於運動集，依照停止時光遞增排序,應用疾速排序
void fast_sort(Activity *act,int f,int t)
{
 if(f<t)
 {
 int i = f-1,j = f;
 Activity a = act[t];
 while(j<t)
 {
  if(act[j].end<=a.end)
  {
  i++;
  Activity temp1 = act[i];
  act[i] = act[j];
  act[j] = temp1;
  }
  j++;
 }
 Activity temp2 = act[t];
 act[t] = act[i+1];
 act[i+1] = temp2;
 fast_sort(act,f,i);
 fast_sort(act,i+2,t);
 }
}
//把每個相容的運動集添加到一個教室，使得教室數量起碼
int select_room(Activity *act,int *time,int n)
{
 int i = 1;
 int j = 1;
 int sumRoom;
 //今朝所用的教室數量
 sumRoom = 1; 
 int sumAct;
 //今朝有若干運動被選擇了
 sumAct = 1; 
 //教室1今朝最晚時光為排在最後面的運動的停止時光
 time[1] = act[0].end; 
 //最早停止的運動放在教室1中
 act[0].roomNum = 1; 
 for(i=1;i<n;i++)
 {
 for(j=1;j<=sumRoom;j++)
 {
  //假如運動act[i]的開端時光年夜於等於j教室今朝的最晚停止時光且此運動還沒有被選擇，
  //則此運動與今朝這間教室外面的運動是兼容的，可以參加出來
  if((act[i].begin>=time[j])&&(!act[i].flag))
  {
  //此運動的教室號碼
  act[i].roomNum = j;
  //此運動被選擇
  act[i].flag = true;
  //更新此教室的最晚時光
  time[j] = act[i].end;
  //被選擇的運動數量加1
  sumAct ++;
  }
 }
 //解釋運動沒有全體被選擇，而一切運動都遍歷一遍
 //所以須要再加一個教室，從頭再遍歷
 if(sumAct<n&&i==n-1)
 {
  //從頭開端遍歷
  i = 0;
  //教室數量加1
  sumRoom = sumRoom+1;
 }
 }
 return sumRoom;
}

int _tmain(int argc, _TCHAR* argv[])
{
 int cases;
 Activity act[N];
 //用來記載每一個教室今朝最晚完成的運動的停止時光
 int time[N];
 cout<<"請輸出案例的個數："<<endl;
 cin>>cases;
 while(cases--)
 {
 int n;
 cout<<"請輸出運動的數量："<<endl;
 cin>>n;
 int i;
 for(i=0;i<n;i++)
 {
  time[i+1] = 0; //初始化每一個教室今朝最晚的時光為0
  act[i].number = i+1;
  act[i].flag = false;  //初始化每一個運動都未被選擇
  act[i].roomNum = 0; //初始化每一個運動都占用教室
  cout<<"運動"<<i+1<<"開端時光：";
  cin>>act[i].begin;
  cout<<"運動"<<i+1<<"停止時光：";
  cin>>act[i].end;
 }
 fast_sort(act,0,n-1);
 int roomNum =select_room(act,time,n);
 cout<<"所用教室總數為："<<roomNum<<endl;
 cout<<"每一個運動在哪個教室中："<<endl;
 for(i=0;i<n;i++)
 {
  cout<<"運動"<<act[i].number<<"在教室"<<act[i].roomNum<<"中"<<endl;
 }
 }
 system("pause");
 return 0;
}