// cw4_EULER2.cpp : Defines the entry point for the console application.
#include "stdafx.h"
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <sstream>
#include <string>
#include <chrono>
#include <conio.h>
#include <algorithm>
#include <stdlib.h>
#include<stdio.h>
using namespace std;

//--------------------------------------------------------------------ZAPIS DO PLIKU--------------------------------------------------------------------
int saveArrayWyniki(double *wyniki[], int start, int krok, int liczbaPomiarow)
{
	fstream plik("plik-wyniki.txt", ios::out);
	if (plik.good())
	{
		plik << "wierzcholki \tDYNAMICZNE \tDOKLADNE \tZACHLANNE" << endl;
		for (int i = 0; i < liczbaPomiarow; i++)
		{
			plik << start << "\t";
			for (int j = 0; j < 3; j++)
			{
				plik << wyniki[j][i] << "\t";
				plik.flush();
			}
			start += krok;
			plik << endl;
		}
		plik.close();
	}
	return(0);
}
//--------------------------------------------------------------------DYNAMICZNE--------------------------------------------------------------------

int max(int a, int b) { return (a > b) ? a : b; }

// Returns the maximum value that can be put in a dynamic of capacity W
int dynamic(int W, int wt[], int val[], int n)
{
	int i, w;
	int **K = new int*[n + 1];
	for (int m = 0; m < n + 1; m++) {
		K[m] = new int[W + 1];
	}

	// Build table K[][] in bottom up manner
	for (i = 0; i <= n; i++)
	{
		for (w = 0; w <= W; w++)
		{
			if (i == 0 || w == 0)
				K[i][w] = 0;
			else if (wt[i - 1] <= w)
				K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w]);
			else
				K[i][w] = K[i - 1][w];
		}
	}

	return K[n][W];
}

//--------------------------------------------------------------------DOKLADNE--------------------------------------------------------------------

// Returns the maximum value that can be put in a brutforce of capacity W
int brutforce(int W, int wt[], int val[], int n)
{
	// Base Case
	if (n == 0 || W == 0)
		return 0;

	// If weight of the nth item is more than brutforce capacity W, then
	// this item cannot be included in the optimal solution
	if (wt[n - 1] > W)
		return brutforce(W, wt, val, n - 1);

	// Return the maximum of two cases:
	// (1) nth item included
	// (2) not included
	else return max(val[n - 1] + brutforce(W - wt[n - 1], wt, val, n - 1),
		brutforce(W, wt, val, n - 1)
	);
}

//--------------------------------------------------------------------ZACHLANNE--------------------------------------------------------------------
struct przedmiot
{
	int waga;
	int wartosc;
	double stosunek;
};

int compare2(const void * a, const void * b)
{

	przedmiot *orderA = (przedmiot *)a;
	przedmiot *orderB = (przedmiot *)b;

	if (orderB->stosunek > orderA->stosunek)
	{
		return 1;
	}
	else if (orderB->stosunek < orderA->stosunek)
	{
		return -1;
	}
	else
	{
		return 0;
	}
}

int zachlanny(int W, int w[], int p[], int n, int sum = 0, int waga = 0)
{
	int i;
	przedmiot *przedmioty = nullptr;
	przedmioty = new przedmiot[n];
	for (i = 0; i < n; i++)
	{
		//cout << p[i] << " " << w[i] << endl;
		przedmioty[i].stosunek = (double)p[i] / w[i];
		//cout << "przedmioty[i].stosunek to: " << przedmioty[i].stosunek << endl;
		przedmioty[i].waga = w[i];
		przedmioty[i].wartosc = p[i];
	}

	qsort(przedmioty, n, sizeof(przedmiot), compare2);
	int a = 0;
	while (waga <= W && a < n)
	{
		if (waga + przedmioty[a].waga <= W)
		{
			waga += przedmioty[a].waga;
			sum += przedmioty[a].wartosc;
		}
		a++;
	}
	delete[] przedmioty;
	//cout << "Zachlanny: " << sum << endl; //usuniete za ostatnim razem
	return 0;
}


//--------------------------------------------------------------------MAIN FUNCTION--------------------------------------------------------------------

int compare(const void * a, const void * b)
{
	return (*(int*)a - *(int*)b);
}

int main()
{
	//printf_s("%lf",nasycenie[1]);
	int liczbaPomiarow = 10;
	int liczbaPowtorzen = 1;
	int startNode = 50;
	int krok = 50;


	double **wyniki = new double*[3];
	for (int i = 0; i < 3; i++)
		wyniki[i] = new double[liczbaPomiarow];

	int pojemnosc = startNode;

	for (int petlaPomiaru = 0; petlaPomiaru < liczbaPomiarow; petlaPomiaru++)
	{
		int liczbaWyrazow = pojemnosc / 2 + 1;
		int maxWaga = pojemnosc / 2 + 1;
		int maxWartosc = pojemnosc / 2 + 1;


		int *weight = new int[liczbaWyrazow];
		int *volume = new int[liczbaWyrazow];
		srand(time(0));
		double sumaPom[3] = { 0 };
		for (int petlaPowtorzen = 0; petlaPowtorzen < liczbaPowtorzen; petlaPowtorzen++)
		{
			for (int i = 0; i < liczbaWyrazow; i++)
			{
				weight[i] = rand() % maxWaga + 1;
				volume[i] = rand() % maxWartosc + 1;
			}
			qsort(weight, liczbaWyrazow, sizeof(int), compare);

			auto startTime = std::chrono::high_resolution_clock::now();
			dynamic(pojemnosc, weight, volume, liczbaWyrazow);
			auto finish = std::chrono::high_resolution_clock::now();
			sumaPom[0] = ((finish - startTime).count());

			startTime = std::chrono::high_resolution_clock::now();
			brutforce(pojemnosc, weight, volume, liczbaWyrazow);
			finish = std::chrono::high_resolution_clock::now();
			sumaPom[1] = ((finish - startTime).count());

			startTime = std::chrono::high_resolution_clock::now();
			zachlanny(pojemnosc, weight, volume, liczbaWyrazow);
			finish = std::chrono::high_resolution_clock::now();
			sumaPom[2] = ((finish - startTime).count());

			delete[] weight;
			delete[] volume;
		}

		for (int k = 0; k < 3; k++)
		{
			wyniki[k][petlaPomiaru] = sumaPom[k] / liczbaPowtorzen;
			cout << wyniki[k][petlaPomiaru] << "\t";

		}
		cout << endl;
		pojemnosc += krok;

	}

	saveArrayWyniki(wyniki, startNode, krok, liczbaPomiarow);
	return 0;
}