rucsac (discreta)

#include<stdio.h>

int maxim(int a, int b)
{
    if(a > b) return a;
    return b;
}

int main()
{
    int n, G, i, j, cmax[101][101], c[101], g[101];

    FILE *f = fopen("rucsac.txt", "r");

    fscanf(f, "%d", &G);
    fscanf(f, "%d", &n);

    for(i = 1; i <= n; i++)
        fscanf(f, "%d %d", &c[i], &g[i]);

    fclose(f);

    for (i = 1; i <= n; i++)
        for (j = 1; j <= G; j++)
        {
            cmax[i][j] = cmax[i-1][j];
            if((g[i] <= j) && (cmax[i-1][j-g[i]] + c[i] > cmax[i-1][j]))
                cmax[i][j] = cmax[i-1][j-g[i]] + c[i];
        }

    printf("Castig maxim: %d\n", cmax[n][G]);

    printf("Obiectele selectate:\n");

    i = n, j = G;
    while(i >= 1)
    {
        if(cmax[i][j] != cmax[i-1][j])
        {
            printf("%d ", i);
            j = j - g[i];
        }
        i--;
    }

    return 0;
}