#include <stdio.h>
#include <stdlib.h>
#include<time.h>
typedef struct
{
    int gr;
    int p;
} obiect;
void back(int n, obiect *ob, int g, int *mprofit, int profit, int greutate, int k)
{
    if (k == n || greutate == g)
    {
        if (profit > *mprofit)
        {
            *mprofit = profit;
        }
    }
    for (int i = k; i < n; i++)
    {
        if (ob[k].gr + greutate <= g)
        {
            greutate += ob[k].gr;
            profit += ob[k].p;
            back(n, ob, g, mprofit, profit, greutate, i + 1);
            greutate -= ob[k].gr;
            profit -= ob[k].p;
        }
    }
}
int main()
{
    clock_t start_time = clock();
    clock_t end;
    double time_used=0;
    int g = 0;
    int n = 0;
    int mprofit = 0;
    printf("Introduceti numarul de obiecte si capacitatea rucsacului");
    scanf("%d%d", &n, &g);
    obiect *ob;
    ob = malloc(sizeof(obiect) * n);
    for (int i = 0; i < n; i++)
    {
        printf("ob[%d].greutate=", i);
        scanf("%d", &ob[i].gr);
        printf("ob[%d].profit=", i);
        scanf("%d", &ob[i].p);
    }
    back(n, ob, g, &mprofit, 0, 0, 0);
    printf("mprofit:%d\n", mprofit);
    end=clock();
    time_used=((double) (end - start_time)) / CLOCKS_PER_SEC;
    printf("%f",time_used);
    return 0;
}