#include <iostream>
#include <cstdlib>
#include <chrono>
#include <iomanip>

using namespace std;
using namespace std::chrono;

int counter_knapSack = 0;
int counter_metodaZachlanna = 0;

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

double knapSack(int W, double* wt, double* val, int n) {
    counter_knapSack++;

    auto startTime = high_resolution_clock::now();

    if (n == 0 || W == 0)
        return 0;

    if (wt[n - 1] > W)
        return knapSack(W, wt, val, n - 1);
    else
        return max(
                val[n - 1] + knapSack(W - wt[n - 1], wt, val, n - 1),
                knapSack(W, wt, val, n - 1)
        );

    auto endTime = high_resolution_clock::now();
    auto elapsedTime = duration_cast<nanoseconds>(endTime - startTime).count();
    double timeInNanoseconds = static_cast<double>(elapsedTime);

    cout << "Czas wykonania knapSack: " << fixed << setprecision(0) << timeInNanoseconds << " nanosekund" << endl;
}

void generowanie_liczb(double* cena, double* waga, int* index, int n) {
    for (int i = 0; i < n; i++) {
        cena[i] = (rand() % 600) / 100.0;
        waga[i] = (rand() % 600) / 100.0;
        index[i] = i;
    }
}

void wyswietlanie_produktow(double* cena, double* waga, int* index, int n) {
    cout << "Produkty:" << endl;
    for (int i = 0; i < n; i++) {
        cout << "Produkt " << index[i] << ": Cena=" << cena[i] << ", Waga=" << waga[i] << endl;
    }
}

double metoda_zachlanna(double* cena, double* waga, int* index, int n, int pojemnosc) {
    counter_metodaZachlanna++;

    auto startTime = high_resolution_clock::now();

    double saldo = 0.0;
    double* oplacalnosc = new double[n];
    for (int i = 0; i < n; i++) {
        oplacalnosc[i] = cena[i] / waga[i];
    }
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++)
            if (oplacalnosc[j] < oplacalnosc[j + 1]) {
                swap(cena[j], cena[j + 1]);
                swap(waga[j], waga[j + 1]);
                swap(oplacalnosc[j], oplacalnosc[j + 1]);
                swap(index[j], index[j + 1]);
            }
    }

    for (int i = 0; i < n; i++) {
        if (pojemnosc - waga[i] >= 0) {
            pojemnosc -= waga[i];
            saldo += cena[i];
        }
    }

    delete[] oplacalnosc;

    auto endTime = high_resolution_clock::now();
    auto elapsedTime = duration_cast<nanoseconds>(endTime - startTime).count();
    double timeInNanoseconds = static_cast<double>(elapsedTime);

    cout << "Czas wykonania metoda_zachlanna: " << fixed << setprecision(0) << timeInNanoseconds << " nanosekund" << endl;

    return saldo;
}

int main() {
    srand(time(NULL));

    int ilosc;
    double alg_aproksymacyjny;
    double alg_dokladny;

    cout << "Podaj ile egzemplarzy danych wygenerowac: ";
    cin >> ilosc;

    int n;
    cout << "Podaj ile przedmiotów chcesz wygenerowac: ";
    cin >> n;

    double pojemnosc;
    cout << "Podaj pojemność plecaka: ";
    cin >> pojemnosc;

    printf("Algorytm aproksymacyjny Algorytm dokladny Dokladnosc\n");
    for (int i = 0; i < ilosc; i++) {
        double* cena = new double[n];
        double* waga = new double[n];
        int* index = new int[n];

        generowanie_liczb(cena, waga, index, n);

        counter_knapSack = 0;
        counter_metodaZachlanna = 0;

        auto startZachlanna = high_resolution_clock::now();
        alg_aproksymacyjny = metoda_zachlanna(cena, waga, index, n, pojemnosc);
        auto endZachlanna = high_resolution_clock::now();
        auto czas_zachlanna = duration_cast<nanoseconds>(endZachlanna - startZachlanna).count();

        auto startKnapSack = high_resolution_clock::now();
        alg_dokladny = knapSack(pojemnosc, waga, cena, n);
        auto endKnapSack = high_resolution_clock::now();
        auto czas_knapsack = duration_cast<nanoseconds>(endKnapSack - startKnapSack).count();

        printf("%.2f %.2f %.2f\n", alg_aproksymacyjny, alg_dokladny, alg_aproksymacyjny / alg_dokladny * 100);
        cout << "Czas wykonania metoda_zachlanna: " << fixed << setprecision(0) << czas_zachlanna << " nanosekund" << endl;
        cout << "Czas wykonania knapSack: " << fixed << setprecision(0) << czas_knapsack << " nanosekund" << endl;
        cout << "Liczba operacji metoda_zachlanna: " << counter_metodaZachlanna << endl;
        cout << "Liczba operacji knapSack: " << counter_knapSack << endl;

        delete[] cena;
        delete[] waga;
        delete[] index;
    }

    return 0;
}