#include <assert.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

static void** array_2d(size_t _row, size_t _col, size_t _size_m)
{
    char* ptr, ** arr;
    size_t i;

    arr = (char**)malloc(sizeof(char*) * _row + _size_m * _col * _row);
    if (!arr) return 0; //Memory allocation failed

    // ptr is now pointing to the first element in of 2D array
    ptr = (char*)(arr + _row);

    // for loop to point rows pointer to appropriate location in 2D array
    for (i = 0; i < _row; i++)
    {
        arr[i] = ((char*)(ptr + _col * i * _size_m));
    }
    return (void**)arr;
}

/*
* 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");

    fin >> (*n);
    fin >> (*W);
    obiecte->resize(*n);
    for (int i = 0; i < *n; i++)
    {
        fin >> (*obiecte)[i].greutate;
        fin >> (*obiecte)[i].profit;
    }
    fin.close();
}

static int knapSack_greedy(int W, obiect_rucsac* _Multime, int** K, 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;
}

int main()
{
    int n, g;
    int** K;
    std::vector<obiect_rucsac> _Multime;
    std::ofstream fout("rucsac.out");

    load_sack(&g, &n, &_Multime);
    K = (int**)array_2d(n + 1, g + 1, sizeof(int));
    assert(K);

    //int ff = knapSack_backtracking(g, _Multime.data(), n);
    int ff = knapSack_greedy(g, _Multime.data(), K, n);
    fout << ff;
    return 0;
}