main.cpp

全国高校BBS程序开发大赛赛题－算法项目

#include <iostream>
#include <vector>
#include <algorithm>
#include <assert.h>
#include <math.h>
#include <time.h>

using namespace std;

const int TASK_NUMBER = 5;


void init_group(const size_t water_num, vector<int> & task_vector, vector< pair<int, vector< int > > > & group,const size_t group_scale);
void cross_over(vector<int> & task_vector,const size_t water_num, vector< pair<int, vector< int > > > & group);
bool select(vector< pair<int, vector< int > > > & group, const size_t group_scale);
int check(vector<int> & task_vector, const size_t water_num, vector<int> & offspring);
void print_group(const vector< pair<int, vector< int > > > &  group, const size_t water_num, vector<int> & task_vector);

class SEQ_IN_PATTERN_CLASS 
{
public:
	SEQ_IN_PATTERN_CLASS(void){
		m_current_time = 0;
		m_seq_total_time = 0;
	}
public:
	size_t m_current_time;
	size_t m_seq_total_time;
	vector<int> m_schedule;
};

class PATTERN_CLASS
{
public:
	PATTERN_CLASS(size_t water_num){
		m_water_num = water_num;
		m_totoal_time=0;

		v=new SEQ_IN_PATTERN_CLASS[m_water_num];
		assert(NULL != v);
	}
	~PATTERN_CLASS(){
		delete [] v;
	}
public:
	size_t m_totoal_time;
	size_t m_water_num;
	SEQ_IN_PATTERN_CLASS  * v;
};


bool compare(int & right, int & left){
	return (right >= left);
}

void main(int argc, char * argv[]){
    
	
	int task_num = 10;
	cout<<"please input the number of tasks : ";
	cin>>task_num;
	
	vector<int>  task_vector;
	for(int i=0; i<task_num; i++){
		int tt;
		cout<<"please input the time needed by the "<<i<<"th task : ";
		cin>>tt;
		task_vector.push_back(tt);
	}

	//task_vector.push_back(44);
	//task_vector.push_back(24);
	//task_vector.push_back(24);
	//task_vector.push_back(22);
	//task_vector.push_back(21);
	//task_vector.push_back(17);
	//task_vector.push_back(8);
	//task_vector.push_back(8);
	//task_vector.push_back(6);
	//task_vector.push_back(6);

	int w_num = 0;
	cout<<"please input the number of water source provided : ";
	cin>>w_num;
	const size_t water_num = w_num  ;
	
	int g_scale;
	cout<<"please input the number of group element : ";
	cin>>g_scale;
	const size_t group_scale = g_scale;//种群有一半是作为offsprings

	/////////////////////////////////////////////////////////////////////////////

	vector< pair<int, vector< int > > > group;
	group.reserve(group_scale);

	sort(task_vector.begin(), task_vector.end());

    srand( (unsigned)time( NULL ));
	init_group(water_num, task_vector, group, group_scale);

	const int COUNT_DIFF = 16;
	const int VALUE_DIFF = 4;
	int count = 0;
	int old_value = 0;
	int new_value = 0;
	
	while ( (count >= 0) && (count < COUNT_DIFF)) {
		cross_over(task_vector,water_num, group);
		
		new_value = select(group, group_scale);

		print_group(group,water_num,task_vector);

		if( (new_value >= old_value) && abs(new_value - old_value) < VALUE_DIFF ){
			count++;			
		}else{ 
			count = 0;
		}

		old_value = new_value;
	}
}

void print_group(const vector< pair<int, vector< int > > > &  group, const size_t water_num, vector<int> & task_vector){
	assert(0 <= group.size());

	cout<<"\n total time ="<<(group[0]).first<<"\n  the schedule is:\n";
	for(size_t i=0; i<water_num; i++){
		cout<<"the "<<i<<"th : ";
		for(size_t j=i; j<group[0].second.size(); j+=water_num){
			int index = ((group[0]).second)[j];
			assert(index>=-1 && index<=((int)task_vector.size()));

			if(-1 != index) cout<<task_vector[index]<<"  ";
		}
		cout<<"\n";
	}
}


void init_group(const size_t water_num,vector<int> & task_vector, vector< pair<int, vector< int > > > & group,const size_t group_scale){
	
	assert((water_num>0)  && (group_scale>0));


	for(size_t i = 0; i < group_scale; i++){
		PATTERN_CLASS patter_vector(water_num);//(各个队列：所有任务用的总时间，单前时间，队列)

		
        for(size_t j = 0; j< task_vector.size(); j++){
			size_t index = rand()%water_num;
			assert(index>=0 && index<patter_vector.m_water_num);

			(patter_vector.v)[index].m_seq_total_time += (patter_vector.v[index].m_current_time +  task_vector[j]);
			(patter_vector.v)[index].m_current_time += task_vector[j];
			(patter_vector.v)[index].m_schedule.push_back(j);            
		}
        patter_vector.m_totoal_time = 0;
		for(size_t j = 0; j< patter_vector.m_water_num; j++){
			patter_vector.m_totoal_time += (patter_vector.v)[j].m_seq_total_time;           
		}

		vector<int> patter_seq;
		int order = 0;
		int pertum = false;
		assert(water_num == patter_vector.m_water_num);
		while( !pertum ){
			assert(order<((int)task_vector.size()));
			pertum = true;
			for(size_t j=0; j < patter_vector.m_water_num; j++){
				int size=(patter_vector.v)[j].m_schedule.size();
				if(order <  size){					
                    patter_seq.push_back((patter_vector.v)[j].m_schedule[order]);
				}else{
					patter_seq.push_back(-1);
				}
				//cout<<order<<" "<<j<<"  "<<size<<"  "<<size-1<<"  "<<(order < (size-1))<<"\n";

				if(order < (size-1) ){
					pertum = false;
				}
			}
			order++;
		}

		//int total_time = 0;
		//for(size_t j = 0; j<patter_vector.size(); j++){
		//	total_time += patter_vector[j].first;
		//	cout<<j<<" ";
		//	for(vector<int>::iterator it = patter_vector[j].second.second.begin(); it != patter_vector[j].second.second.end(); ++it){
		//		cout<<task_vector[(*it)]<<" ";
		//	}
		//	cout<<"\n";
		//}
		//cout<<"total time = "<<total_time;
		//cout<<"\n";
		//for(size_t j=0; j < patter_seq.size(); j++){
		//	if(patter_seq[j] >= 0){
		//		cout<<task_vector[patter_seq[j]]<<" ";
		//	}else{
		//		cout<<0<<" ";
		//	}
		//}
		//cout<<"\n";

		group.push_back(make_pair(patter_vector.m_totoal_time, patter_seq) );
	}

}

void cross_over(vector<int> & task_vector,const size_t water_num, vector< pair<int, vector< int > > > & group){
	size_t group_size = group.size();
	size_t cutpoint1 = 0;
	size_t cutpoint2 = 0;
	size_t parent1 = 0;
	size_t parent2 = 0;

	for(size_t i = 0; i < group_size/2; i++){
		parent1 = rand()%group_size;
		assert(group[parent1].second.size() > 0);
		cutpoint1 = rand()%( (group[parent1].second).size() );
		///////////////////////////////////////////////////////////////////////////////////////////////////////////
		//cout<<"cut1 = "<<cutpoint1<<"\n";
		//for(vector<int>::iterator it = (group[parent1].second).begin(); it != (group[parent1].second).end(); ++it){
		//	cout<<"  "<<(*it);
		//}
		//cout<<"\n";
		////////////////////////////////////////////////////////////////////////////////////////////////////////////


		parent2 = rand()%group_size;
		assert(group[parent2].second.size() > 0);
		cutpoint2 = rand()%( (group[parent2].second).size() );
		//////////////////////////////////////////////////////////////////////////////////////////////////////////
		//cout<<"cut2 = "<<cutpoint2<<"\n";
		//for(vector<int>::iterator it = (group[parent2].second).begin(); it != (group[parent2].second).end(); ++it){
		//	cout<<"  "<<(*it);
		//}
		//cout<<"\n";
		////////////////////////////////////////////////////////////////////////////////////////////////////////////
		

		vector<int> offspring1;
		vector<int> offspring2;

		size_t j1 = 0;
		size_t j2 = 0;
		for(j1 = 0; j1<cutpoint1; j1++){
            offspring1.push_back( (group[parent1].second)[j1] );
		}
		for(j2 = 0; j2<cutpoint2; j2++){
			offspring2.push_back( (group[parent2].second)[j2] );
		}
		for(; j1 < (group[parent1].second).size(); j1++ ){
			offspring2.push_back( (group[parent1].second)[j1] );
		}
		for(; j2 < (group[parent2].second).size(); j2++ ){
			offspring1.push_back( (group[parent2].second)[j2] );
		}

		int cost_time = check(task_vector, water_num, offspring1);		
		group.push_back( make_pair(cost_time, offspring1) );
		
		cost_time = check(task_vector, water_num, offspring2);
		group.push_back( make_pair(cost_time, offspring2) );
		
		/////////////////////////////////////////////////////////////////////////////////////////////////////////////
		//cout<<"offspring1: ";
		//for(vector<int>::iterator it = offspring1.begin(); it != offspring1.end(); ++it){
		//	cout<<"  "<<(*it);
		//}
		//cout<<"\n";

		//cout<<"offspring2: ";
		//for(vector<int>::iterator it = offspring2.begin(); it != offspring2.end(); ++it){
		//	cout<<"  "<<(*it);
		//}
		//cout<<"\n";
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////
	}
        
}

int check(vector<int> & task_vector, const size_t water_num, vector<int> & offspring){

	vector< vector<int> >  patter_vector;//(单前队列各个任务用的总时间，单前时间，队列)
	patter_vector.reserve(water_num);
	for(size_t i=0; i<water_num; i++){
		vector<int> seq;
		patter_vector.push_back(seq);
	}

	bool * flag = new bool[task_vector.size()];
	assert(flag);
	for(size_t i = 0; i < (task_vector.size()); i++){
        flag[i] = false;
	}

	size_t index = 0;
	for(size_t i = 0; i < (offspring.size()); i++){
		index = i%water_num;
		if((offspring[i] >= 0) && !flag[offspring[i]]){
			flag[offspring[i]] = true;
			patter_vector[index].push_back(offspring[i]);  
		}
	}

	for(size_t i = 0; i<task_vector.size(); i++){
		if( !flag[i] ){
			index = rand()%water_num;
			patter_vector[index].push_back(i);
		}
	}
	for(size_t i = 0; i<patter_vector.size(); i++){
		sort(patter_vector[i].begin(), patter_vector[i].end());
	}
	

	offspring.clear();

	vector<int> & patter_seq = offspring;
	int order = 0;
	int pertum = false;
	assert(water_num == patter_vector.size());
	while( !pertum ){

		pertum = true;
		
		for(size_t j=0; j < patter_vector.size(); j++){	
			int size = patter_vector[j].size();		
			if(order < size ){					
                patter_seq.push_back(patter_vector[j][order]);
			}else{
				patter_seq.push_back(-1);
			}
			//cout<<order<<" "<<j<<"  "<<size<<"  "<<size-1<<"  "<<(order < (size -1) )<<"\n";

			if(order < (size -1) ){
				pertum = false;
			}
		}
		order++;
	}
	
	int total_time = 0;
	for(size_t j = 0; j<patter_vector.size(); j++){
		int seq_time = 0;
		int temp_time = 0;
		//cout<<j<<" ";
		for(vector<int>::iterator it = patter_vector[j].begin(); it != patter_vector[j].end(); ++it){
			seq_time = seq_time + (temp_time + task_vector[(*it)]);
			temp_time += task_vector[(*it)];
			//cout<<task_vector[(*it)]<<" ";
		}
		total_time += seq_time;
		//cout<<"\n";
	}
	//cout<<"total time = "<<total_time;
	//cout<<"\n";
	//for(size_t j=0; j < patter_seq.size(); j++){
	//	if(patter_seq[j] >= 0){
	//		cout<<" <"<<patter_seq[j]<<" , "<<task_vector[patter_seq[j]]<<">  ";
	//	}else{
	//		cout<<0<<" ";
	//	}
	//}
	//cout<<"\n";


	return total_time;
}
 
bool select(vector< pair<int, vector< int > > > & group, size_t group_scale){

	sort(group.begin(), group.end());

	//print_group(group);

	vector< pair<int, vector< int > > >::iterator new_end = unique(group.begin(), group.end());
	group.erase(new_end, group.end());
    
	if(group_scale >= group.size()) return true;
	else{
        new_end = group.begin();
		for(size_t i = 0; i<group_scale; i++){
            new_end++;
		}
		group.erase(new_end,group.end());
	}

	//print_group(group);

    return true;
}