//optymalizacja-tabu.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream"
#include "conio.h"

#define MAX 100

using namespace std;

int n, lineN = 0, lineLTS = 0;                           
int N[1225][MAX], LTS[100][MAX];         
long int F_N[1225];

void drukuj(const int *pi, const int n) 
{
	if (pi != 0)
	{
		for (int k = 0; k < n; k++)
		{
			N[lineN][k] = pi[k];
		}
		lineN++;
	}
}

void otoczenie(int n, int *pi)      
{
	int tmp = 0;
	for (int i=0; i<(n * (n - 1))/2; i++)
	{
		for(int j=i+1; j<=n-1; j++)
		{
			tmp = pi[i];
			pi[i] = pi[j];
			pi[j] = tmp;
			drukuj(pi, n);
			tmp = pi[i];
			pi[i] = pi[j];
			pi[j] = tmp;
		}
	}
	lineN = 0;
}

int maks(int T)
{
	if (T > 0)
		return T;
    else
		return 0;
}


void Fcelu(int n, int *t, int *d, int *w)
{
	long int T, F = 0, c = 0;
	
	for (int a = 0; a < n*(n-1)/2; a++)
	{
		for (int b = 0; b < n; b++)
		{
			c = c + t[N[a][b]];
			T = maks(c - d[N[a][b]]);
			F = F + T * w[N[a][b]];
		}
		F_N[a] = F;
		c = 0;
		F = 0;
	}
}

int lepszy(long int F_piBest, long int F_pi)
{
	if(F_piBest > F_pi)
		return 1;
	else
		return 0;
}

int main(int argc, char* argv[])
{
	int t[MAX], w[MAX], d[MAX], pi[MAX], piBest[MAX], licznik = 0;
	long int F_piBest = 0;    
	bool OK = 0;
	
	do
	{
		cout << "Prosze wprowadzic liczbe zadan: ";
		cin >> n;
		cout << endl;

		if (n >= 2 && n <= MAX) 
		{
			OK = true;
		}
		else
		{
			cout << endl;
			cout << "Program dziala tylko dla ilosci zadan z przedialu 2 - "<< MAX << "!"  << endl;
		}

	}
	while (!OK);
	
	if (n <= MAX)
	{
		for (int l = 0; l<n; l++)
		{
			cout << "Podaj CZAS wykonania zadania nr\t" << l + 1 << "\t: ";
			cin >> t[l];
			
			cout << "Podaj WAGE zadnia nr\t\t" << l + 1 << "\t: ";
			cin >> w[l];
			
			cout << "Podaj DEADLINE zadania nr\t" << l + 1 << "\t: ";
			cin >> d[l];
			cout << endl;
		}
	}
	else
	{
		cout << endl;
	}
	
	for(int m=0; m<n; m++)
	{
		cout << "Zadanie nr " << m+1 << ": " << endl;
		cout << "\t- czas wykonania: \t" << ": " << t[m] << endl;
		cout << "\t- waga :\t\t" << ": " << w[m] << endl;
		cout << "\t- deadline :\t\t" << ": " << d[m] << endl;
		cout << endl;
	}
	for (int a = 0; a < MAX; a++)
	{
		pi[a] = a;
	}
	
	for (int b = 0; b < 1225; b++)
	{
		for(int c = 0; c < MAX; c++)
		{
			N[b][c] = 0;
		}
	}
	for (int d = 0; d < 100; d++)
	{
		for(int e = 0; e < MAX; e++)
		{
			LTS[d][e] = 0;
		}
	}
	
	for (int f = 0; f < MAX; f++)
	{
		piBest[f] = pi[f];
		LTS[lineLTS][f] = piBest[f];
	}
	lineLTS++;
	
	long int T_piBest, c_piBest = 0;
	
	for (int z = 0; z < n; z++)
	{
		c_piBest = c_piBest + t[piBest[z]];
		T_piBest = maks(c_piBest - d[piBest[z]]);
		F_piBest = F_piBest + T_piBest * w[piBest[z]];
	}

	for (int r = 0; r < (n); r++)
	{
		otoczenie(n, pi);
		Fcelu(n, t, d, w);

		for (int k = 0; k < (n*(n-1)/2); k++)
		{
			for (int j=0; j < lineLTS; j++)
			{
				for(int i = 0; i < n; i++)
				{
					if (N[k][i] == LTS[j][i]) licznik += 1;
				}
				if (licznik == n)
				{
					if (!lepszy(F_piBest, F_N[k]))
					{
						F_N[k] = LONG_MAX;
					}
				}
				licznik = 0;
			}
		}
		int best = F_N[0];
		int indeks = 0;
		
		for (int l = 1; l < (n*(n-1)/2); l++)
		{
			if(lepszy(best, F_N[l]))
			{
				best = F_N[l];
				indeks = l;
			}
		}
		
		if (lepszy(F_piBest, F_N[indeks]))
		{
			for (int m = 0; m < n; m++)
			{
				piBest[m] = N[indeks][m];
			}
			F_piBest = F_N[indeks];
		}
		
		for (int p = 0; p < n; p++)
		{
			pi[p] = N[indeks][p];
			LTS[lineLTS][p] = pi[p];
		}
		lineLTS++;
	}
	
	cout << endl;
	cout << "Optymalna kolejnosc wykonania zadan to:" << endl;
	
	for(int o = 0; o < n; o++)
	{
		cout << piBest[o] +1 << "  ";
	}
	
	cout << endl;
	cout << "Wcisnij dowolny klawisz aby kontynuowaĉ..." << endl;
	_getch();
	return 0;
}


