#ifndef __RUCSAC_C__
#define __RUCSAC_C__

#include<stdio.h>
#include<string.h>
#include <time.h>
#include <vector>
#include <iostream>
#include <fstream>

#ifndef min(X, Y)
#define min(X, Y) (((X) < (Y)) ? (X) : (Y))
#endif // !MIN

#ifndef max(X, Y)
#define max(X, Y) (((X) > (Y)) ? (X) : (Y))
#endif // !MAX

/*
* 2. Rezolvati problema discreta a rucsacului pentru valori mici ale lui N (<=15) folosind backtracking si comparati
* timpii de executie intre Backtracking si Greedy. Comparati de asemenea "calitatea" solutiei oferite de greedy, 
* considerand solutia oferita de backtracking ca referinta. Reprezentati grafic datele pentru valori ale lui N de la 5 la 15.
* N : vector of objects
* G : Max weight
* W : weight (greutate)
* P : Profit
*/
typedef struct obiect_rucsac
{
	int greutate;
	int profit;
}obiect_rucsac;

static void load_sack(int* W, int* n, std::vector<obiect_rucsac> *obiecte)
{
	std::ifstream fin("rucsac.in");
	int tmp;
	fin >> (*n);
	fin >> (*W);
	obiecte->resize(*n);
	for (int i = 0; i < *n; i++)
	{
		fin >> (*obiecte)[i].greutate;
		fin >> (*obiecte)[i].profit;
	}
	fin.close();
}

// Returns the maximum value that can be
// put in a knapsack of capacity W
static int knapSack_backtracking(int W, obiect_rucsac obiecte[], int n)
{
    // Base Case
    if (n == 0 || W == 0) return 0;

    // If weight of the nth item is more than
    // Knapsack capacity W, then this item cannot
    // be included in the optimal solution
    if (obiecte[n - 1].greutate > W) {
        return knapSack_backtracking(W, obiecte, n - 1);
    }

    // Return the maximum of two cases:
    // (1) nth item included
    // (2) not included
    else {
        return max(obiecte[n - 1].profit + knapSack_backtracking(W - obiecte[n - 1].greutate, obiecte, n - 1), knapSack_backtracking(W, obiecte, n - 1));
    }
        
}

//#define N_ELEM 17
//static int test_rucsac_backtracking()
//{
//	obiect_rucsac _Multime[] = {{4, 7}, {5, 2},{9, 3}, {1, 3},{7, 8},
//								{4, 8}, {2, 3}, {2, 3} ,{1, 5}, {1, 1},
//								{11, 20}, {7, 9}, {10, 4}, {12, 10}, {8, 12},
//								{13, 22}, {23, 222} };
//
//	int msec = 0, i, sum=0, val;
//	clock_t before, difference;
//	for (int n = 5; n <= N_ELEM; n++)
//	{
//		for (int g = 0; g < 100; g++)
//		{
//			sum = 0;
//			int ff = knapSack_backtracking(g, _Multime, n);
//			for (i = 0; i < 10; i++)
//			{
//				randomize(_Multime, n, sizeof(obiect_rucsac));
//				before = clock();
//				val = knapSack_backtracking(g, _Multime, n);
//				if (ff != val) printf("Error g:%d n:%d val:%d gg:%d\n", g, n, val, ff);
//				difference = clock() - before;
//				sum += difference;
//			}
//			msec = sum * 1000 / CLOCKS_PER_SEC / (i);
//			printf("%d;%d;%d;%d\n",  n, g,val, msec);
//		}
//
//	}
//
//	return 0;
//}


/*===========================================================================================================================*/
#define N_ELEM 17
#define WEIGHT 100

static int knapSack_greedy(int W, obiect_rucsac _Multime[N_ELEM], int K[N_ELEM + 1][WEIGHT + 1], int n)
{
    int i, w;

    for (i = 0; i <= n; i++)
    {
        for (w = 0; w <= W; w++)
        {
            if (i == 0 || w == 0) K[i][w] = 0;
            else if (_Multime[i - 1].greutate <= w) K[i][w] = max(_Multime[i - 1].profit + K[i - 1][w - _Multime[i - 1].greutate], K[i - 1][w]);
            else K[i][w] = K[i - 1][w];
        }
    }

    //// stores the result of Knapsack
    int res = K[n][W];
	return res;
}


//static int test_rucsac_greedy()
//{
//	obiect_rucsac _Multime[] = { {4, 7}, {5, 2},{9, 3}, {1, 3},{7, 8},
//								{4, 8}, {2, 3}, {2, 3} ,{1, 5}, {1, 1},
//								{11, 20}, {7, 9}, {10, 4}, {12, 10}, {8, 12},
//								{13, 22}, {23, 222} };
//	int K[N_ELEM + 1][WEIGHT + 1];
//	int msec = 0, i, sum = 0, val;
//	clock_t before, difference;
//
//	for (int n = 5; n <= N_ELEM; n++)
//	{
//		for (int g = 0; g < WEIGHT; g++)
//		{
//			sum = 0;
//			int ff = knapSack_greedy(g, _Multime, K, n);
//			for (i = 0; i < 10; i++)
//			{
//				randomize(_Multime, n, sizeof(obiect_rucsac));
//				before = clock();
//				val = knapSack_greedy(g, _Multime, K, n);
//				if (ff != val) printf("Error g:%d n:%d val:%d gg:%d\n", g, n, val, ff);
//				difference = clock() - before;
//				sum += difference;
//			}
//			msec = sum * 1000 / CLOCKS_PER_SEC / (i);
//
//			printf("%d;%d;%d;%d\n", n, g, val, msec);
//		}
//
//	}
//}
/*===========================================================================================================================*/


// Comparison function to sort Item according to val/weight ratio
static int cmp_obj(const void *_a, const void *_b)
{
	obiect_rucsac *a, *b;
	a = (obiect_rucsac*)_a;
	b = (obiect_rucsac*)_b;

    double r1 = (double)a->profit / (double)a->greutate;
    double r2 = (double)b->profit / (double)b->greutate;
    if (r1 > r2) return 1;
    else if (r1 < r2) return -1;
    else return 0;
}

// Main greedy function to solve problem
static double knapSack_fractional(int W, obiect_rucsac arr[], int n)
{
    //sorting Item in base of ratio
    qsort(arr, n, sizeof(obiect_rucsac), cmp_obj);

    double finalvalue = 0.0; // Result (value in Knapsack)

    for (int i = 0; i < n; i++) {
        // If adding Item doesent overflow, add it completely
        if (arr[i].greutate <= W) {
            W -= arr[i].greutate;
            finalvalue += arr[i].profit;
        }
        else {      // add part of iteam
            finalvalue += arr[i].profit * ((double)W / (double)arr[i].greutate);
            break;
        }
    }
    return finalvalue;
}

// Driver code
static int test_rucsac_fractional()
{
    int W = 50; //    Weight of knapsack
    obiect_rucsac _Multime[] = { {4, 7}, {5, 2},{9, 3}, {1, 3},{7, 8},
                            {4, 8}, {2, 3}, {2, 3} ,{1, 5}, {1, 1},
                            {11, 20}, {7, 9}, {10, 4}, {12, 10}, {8, 12},
                            {13, 22}, {23, 222} };

    int n = sizeof(_Multime) / sizeof(_Multime[0]);

    // Function call
    printf("Valoarea maxima: %f\n", knapSack_fractional(W, _Multime, n));
    return 0;
}

int main()
{
    int n, g;
    int K[N_ELEM + 1][WEIGHT + 1];
    std::vector<obiect_rucsac> _Multime;
    std::ofstream fout("rucsac.out");

    load_sack(&g, &n, &_Multime);
    //int ff = knapSack_backtracking(g, _Multime.data(), n);
    int ff = knapSack_greedy(g, _Multime.data(), K, n);
    fout << ff;
    return 0;
}
#endif // !__RUCSAC_C__