Wednesday, October 20, 2010

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;
}

No comments:

Post a Comment