#include <stdio.h>
#include <stdlib.h>

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

struct ding
{
    int gewicht;
    int wert;
};

int** rucksackmatrix(ding* dinge, int n, int grenze)
{
    int** a = (int**) calloc(n+1, sizeof(int*));
    for(int i = 0; i < n+1; i++) {
        a[i] = (int*) calloc(grenze+1, sizeof(int));
    }
    for(int i = 1; i < n+1; i++)
    {
        for(int j = 1; j < grenze+1; j++)
        {
 //           printf("i: %i, j: %i, gi: %i, wi: %i\n", i, j, dinge[i-1].gewicht, dinge[i-1].wert);
            if(dinge[i-1].gewicht > j)
                a[i][j] = a[i-1][j];
            else a[i][j] = max(a[i-1][j], a[i-1][j-dinge[i-1].gewicht] + dinge[i-1].wert);
        }
    }
    return(a);
}

ding* rucksacktraceback(ding* dinge, int n, int grenze, int** rsmatrix)
{
    ding* loesung = (ding*) calloc(n+1, sizeof(ding));
    int id = 0;
    for(int i = n, j = grenze; i>0 && j>0;)
    {
       if(rsmatrix[i][j] == rsmatrix[i-1][j]) i--;
       if(rsmatrix[i][j] == rsmatrix[i-1][j-dinge[i-1].gewicht]+dinge[i-1].wert)
       {
           i--; j-=dinge[i].gewicht;
           loesung[id++] = dinge[i];
       }
    }
    //loesung = (ding*) realloc(loesung, (id+1) * sizeof(ding));
    return(loesung);
}

int main()
{
    int grenze = 15, n = 6;

    ding dinge[n];
    dinge[0].gewicht = 2; dinge[0].wert = 7;
    dinge[1].gewicht = 3; dinge[1].wert = 9;
    dinge[2].gewicht = 4; dinge[2].wert = 8;
    dinge[3].gewicht = 7; dinge[3].wert = 8;
    dinge[4].gewicht = 9; dinge[4].wert = 10;
    dinge[5].gewicht = 13; dinge[5].wert = 12;

    int** rsmatrix = rucksackmatrix(dinge, n, grenze);
    for(int i = 0; i < n+1; i++)
    {
        for(int j = 0; j < grenze+1; j++)
            printf("%3i ", rsmatrix[i][j]);
        printf("\n");
    }

    ding* loesung = rucksacktraceback(dinge, n, grenze, rsmatrix);
    int gesgewicht = 0, geswert = 0;
    for(int i = 0; loesung[i].gewicht; i++)
    {
        printf("Gewicht\t%2i Wert\t%2i\n", loesung[i].gewicht, loesung[i].wert);
        gesgewicht+=loesung[i].gewicht;
        geswert+=loesung[i].wert;
    }
    printf("Summe\t%2i \t%2i\n", gesgewicht, geswert);
}