#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int calc_weight(int individual, int length, int** population, int* b);
int calc_value(int individual, int length, int** population, int* a);
void paring(int num, int length, int **population, int **pair);
void one_point_crossover(int crossover_rate,int num, int length, int **population,int **pair);
void mutation(int mutation_rate,int num,int length,int **population);
void roulette_selection(int num,int length,int **population,int *fitness);
void init(int length, int num, int capacity, int** population, int* a, int* b, int* weight, int* value, int* fitness);
int calc_best_id(int* fitness, int num);
double calc_ave(int* fitness, int num);

int main()
{
	
	int **population;//個体集合
	int num;//個体数
	int length;//遺伝子長
	int *weight;
	int *value;
	int *fitness;
	int **pair;
	int crossover_rate;	//交叉確率(%)
	int mutation_rate; //突然変異率(%)
	
	int i,j;
	int a[30], b[30], dummy;
	int capacity = 2000;
	int sedai;
	int best_id;
	int best_value;
	double ave;
	FILE *fp, *fp2;
	int bango;
	char str[256];

	if ((fp = fopen("kekka.csv", "w")) == NULL) {
		printf("File cannot be created.\n");
		return 0;
	}
	num=50;
	length=30;
	crossover_rate=80;
	mutation_rate=1;

	if ((fp2 = fopen("data.csv", "r")) == NULL) {
		printf("File cannot be read.\n");
		return 0;
	}
	else{
		fgets(str,256,fp2);//1行読み飛ばし
		for (i=0; i<length; i++){
			fscanf(fp2,"%d,%d,%d",&dummy, &b[i], &a[i]);
			//printf("%d,%d,%d \n",dummy, b[i], a[i]);
		}
		fclose(fp2);
	}
	

	//個体集合
	population=new int*[num];
	for(i=0;i<num;i++){
		population[i]=new int[length];
	}

	pair=new int*[num];
	for(i=0; i<num; i++){
		pair[i] = new int[length];
	}

	//適応度
	fitness=new int[num];

	//重みと価値
	weight=new int[num];
	value=new int[num];

	//乱数の初期化
	srand( (unsigned)time( NULL ) );
	
	//初期個体の生成
	init(length, num, capacity, population, a, b, weight, value, fitness);

	for (sedai=0; sedai<100; sedai++){

	//paring,交叉
	paring(num, length, population, pair);
	one_point_crossover(crossover_rate,num,length,population,pair);


	//突然変異
	mutation(mutation_rate,num,length,population);

	//適応度の計算
	for (i=0;i<num;i++){
		weight[i]=calc_weight(i,length,population,b);
		value[i]=calc_value(i,length,population,a);
		if (weight[i]>capacity){
			fitness[i] = value[i] - (weight[i]-capacity);
		}
		else{
			fitness[i] = value[i];
		}
	}
	//ルーレット選択
	roulette_selection(num,length,population,fitness);

	for(i=0;i<num;i++){
		weight[i]=calc_weight(i,length,population,b);
		value[i]=calc_value(i,length,population,a);
		if (weight[i]>capacity){
			fitness[i] = value[i] - (weight[i]-capacity);
		}
		else{
			fitness[i] = value[i];
		}
	}
	ave = calc_ave(fitness, num);
	best_id = calc_best_id(fitness, num);
	best_value = fitness[best_id];

	fprintf(fp,"%d,%d,%d,",sedai,best_id,best_value);
	for (i=0; i<length;i++){
		fprintf(fp,"%d",population[best_id][i]);
	}
	fprintf(fp,",%lf\n",ave);


	}
	fclose(fp);

	for(i=0;i<num;i++){
		delete[] population[i];
		delete[] pair[i];
	}
	delete[] population;
	delete[] pair;
	delete[] weight;
	delete[] value;
	
	return 0;
}

int calc_weight(int individual, int length, int** population, int* b){
	int i;
	int weight =0;
	for(i=0;i<length;i++){
		weight = weight + population[individual][i] * b[i] ;
	}
	return weight;
}
int calc_value(int individual, int length, int** population, int* a){
	int i;
	int value = 0;
	for(i=0;i<length;i++){
		value = value + population[individual][i] * a[i] ;
	}
	return value;

}
void paring(int num, int length, int **population, int **pair){
	int *shuffle;
	int r;
	int i,j;
	int temp;

	shuffle=new int[num];

	for(i=0; i<num; i++){
		shuffle[i]=i;
	}

	for(i=0;i<num; i++){
		r=rand() % num;
		temp = shuffle[r];
		shuffle[r] = shuffle[i];
		shuffle[i] = temp;
	}

	for(i=0; i<num; i++){
		for(j=0; j<length; j++){
			pair[i][j] = population[shuffle[i]][j];
		}
	}
}
void one_point_crossover(int crossover_rate,int num,int length,int **population,int **pair){
	int i,j;
	int cross_point;

	for(i=0;i<(num-1);i=i+2){
		if (rand()%100<crossover_rate){
			//交叉実行
			cross_point=rand()%(length-1)+1;
			for (j=0; j<cross_point;j++){
				population[i][j]= pair[i+1][j];
				population[i+1][j] = pair[i][j];
			}
			for (j=cross_point;j<length;j++){
				population[i][j] = pair[i][j];
				population[i+1][j] = pair[i+1][j];
			}
		}
		else
			//交叉を行わず、そのままpairをpopulationにコピー
			for (j=0; j<length;j++){
				population[i][j] = pair[i][j];
				population[i+1][j] = pair[i+1][j];
			}
	}
}
void mutation(int mutation_rate,int num,int length,int **population){
	int i,j;
	for (i=0;i<num;i++){
		for (j=0;j<length;j++){
			if (mutation_rate>rand()%100){
				population[i][j] = 1-population[i][j];
			}
		}
	}
}
void roulette_selection(int num,int length,int **population,int *fitness){
	int i,j,k;
	int sum_fitness;			//適応度の和が入る
	int **new_population;		//選ばれた個体が入る
	double *roulette;			//選択される確率が入る
	double *ac_roulette;		//ルーレットの累積値が入る
	double r;

	new_population=new int*[num];
	for (i=0; i<num; i++){
			new_population[i] = new int[length];
	}

	roulette = new double[num];
	ac_roulette=new double[num];

	//適応度の和を求める
	sum_fitness = 0;
	for (i=0; i<num; i++){
		sum_fitness += fitness[i];
	}

	//ルーレットを作る
	roulette[0] = (double)fitness[0]/(double)sum_fitness;
	ac_roulette[0] = roulette[0];
	for (i=1; i<num; i++){
		roulette[i] = (double)fitness[i] / (double)sum_fitness;
		ac_roulette[i] = ac_roulette[i-1] + roulette[i];
	}

	//ルーレットを使って選択する
	for (i=0; i<num; i++){
		r=(double)rand() / (double)RAND_MAX;
		for (j=0; j<num; j++){
			if (r<=ac_roulette[j]){
				for (k=0; k<length;k++){
					new_population[i][k] = population[j][k];
				}
				break;
			}
		}
	}
	//new populationをpopulationにコピー
	for (i=0;i<num; i++){
		for (k=0; k<length; k++){
			population[i][k] = new_population[i][k];
		}
	}

	delete[] roulette;
	delete[] ac_roulette;

	for (i=0; i<num; i++){
		delete[]new_population[i];
	}
	delete[]new_population;
}
void init(int length, int num, int capacity, int** population, int* a, int* b, int* weight, int* value, int* fitness)
{
	int i, j;
	for(i=0;i<num;i++){
		for(j=0;j<length;j++){
			population[i][j]=rand()%2;
			//printf("%d",population[i][j]);
		}
		
		weight[i]=calc_weight(i,length,population,b);
		value[i]=calc_value(i,length,population,a);
		if (weight[i]>capacity){
			fitness[i] = value[i] - (weight[i]-capacity);
		}
		else{
			fitness[i] = value[i];
		}
	}
}
double calc_ave(int* fitness, int num)
{
	double sum, ave;
	int i;

	sum = 0;
	for (i=0;i<num;i++){
		sum += fitness[i];
	}
	ave = sum / num;
	return ave;
}
int calc_best_id(int* fitness, int num)
{
	int best_id=0;
	int best_value, ave, i;

	best_value=fitness[best_id];
	for (i=1;i<num;i++){
		if (fitness[i]>best_value){
			best_id=i;
			best_value=fitness[i];
		}
	}
	return best_id;
}