\begin{lstlisting}[caption={top-down DP-Implementierung des Rucksackproblems},
	label=knapsack_dp, numbers=left, numberstyle=\tiny, stepnumber=2]
#define UNSET	-1		/* "noch nicht berechnet" Marker */
#define MAX_CAP	1000000		/* max. Kapazitaet */
#define N	5		/* Anzahl der Gegenstandstypen */

int maxKnown[MAX_CAP]; int itemKnown[MAX_CAP];
memset(maxKnown, UNSET, MAX_CAP * sizeof(int));

int knapsack (int cap) {
    int i, space, max, max_i, t;
    if (maxKnown[cap] != UNSET) return maxKnown[cap];
    for (i = 0, max = 0; i < N; i++)
        if ((space = cap - items[i].size) >= 0)
            if ((t = knapsack(space) + items[i].value) > max) {
                max = t;
                max_i = i;
            }
    itemKnown[cap] = items[max_i];
    maxKnown[cap] = max;
    return max;
}
\end{lstlisting}