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