ACM: 624 - CD

Straightforward 0/1 Knapsack problem. Tried malloc, memset, free in 2D array.

CODE

#include <iostream>

enum { TRACK = 30 };

int main(){

    int n, t, d[TRACK];

    int i, j;

    while( scanf("%d%d", &n, &t) != EOF ){

        for(i=0; i<t; ++i)

            scanf("%d", &d[i]);

        //malloc

        bool** pick = (bool**)malloc(t * sizeof(bool*));

        for(i=0; i<t; ++i)

            pick[i] = (bool*)malloc((n+1) * sizeof(bool));

        int* tape = (int*)malloc((n+1) * sizeof(int));

        if( pick == NULL || tape == NULL )

            exit(1);

        for(i=0; i<t; ++i)

            memset(pick[i], 0, (n+1)*sizeof(bool));

        memset(tape, 0, (n+1)*sizeof(int));

        for(i=t-1; i>=0; --i){

            for(j=n; j>=d[i]; --j){

                if( tape[j-d[i]]+d[i] > tape[j] ){

                    tape[j] = tape[j-d[i]] + d[i];

                    pick[i][j] = 1;

                }

            }//j

        }//i

        for(i=0, j=n; i<t; ++i){

            if( pick[i][j] ){

                printf("%d ", d[i]);

                j -= d[i];

            }

        }

        printf("sum:%d\n", tape[n]);

        //free

        for(i=0; i<t; ++i)

            free(pick[i]);

        free(pick);

        free(tape);

    }

    return 0;

}