greedyselector.cpp

贪心算法实现活动安排问题

#include <iostream>
using namespace std;
#include <fstream>
#include "make2db.h"

template <class Type>
void GreedySelector(int n,Type **s,bool *A)
{
	A[1]=true;
	int j=1;
	for(int i=2;i<=n;i++){
		if(s[i][0]>=s[j][1]){
			A[i]=true;
			j=i;
		}else
			A[i]=false;
	}
}

void main(void){
	int n, **kay;
	bool *A;
	int i;
	ifstream fin("data.txt");
	fin>>n;
	Make2DArray(kay,n+1,2);
	Make1DArray(A,n+1);
	
	for (i=1; i<=n; i++)
		fin>>kay[i][0]>>kay[i][1];

	GreedySelector(n, kay,A);
	cout<<"贪心法求得的解是："<<endl;
	cout<<"1["<<kay[1][0]<<", "<<kay[1][1]<<")";
	for (i=2; i<=n; i++)
		if (A[i])
			cout<<ends<<","<<ends<<i<<"["<<kay[i][0]<<", "<<kay[i][1]<<")";
	cout<<endl;

	remove2DArray(kay,n+1);
	remove1DArray(A);
}