1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
|
/* knapsack problem solution with dynamically programming */
#include <stdio.h>
#include <string.h>
#define max_N 300 /* max items */
#define max_V 1000 /* max knapsack volume */
#define max_V1 1001
#define result_length (max_V1 * sizeof( int ))
int V; /* knapsack volume */
int n; /* count of items */
int v[max_N]; /* volume of each item */
int w[max_N]; /* value of each item */
int results[max_N][max_V1]; /* memorized solutions from previous calculations */
int knapsack( const int curr_vol, const int i )
{
if( i < n )
{
/* test, if value was still calculated */
if( results[i][curr_vol] != -1 )
return results[i][curr_vol];
/* calc value without item */
int without_item = knapsack( curr_vol, i + 1 );
/* calc value with item */
int with_item = 0;
if( curr_vol - v[i] >= 0 ) /* if item fits into knapsack */
with_item = w[i] + knapsack( curr_vol - v[i], i + 1 );
/* return max( with_item, without_item ) */
return without_item >= with_item ? without_item : with_item;
}
return 0;
}
int main( void )
{
FILE * ifile = fopen("knapsack.dat", "r");
fscanf( ifile, "%d %d", &V, &n);
for( int i = 0; i < n; ++i )
fscanf( ifile, "%d %d", &v[i], &w[i] );
fclose( ifile );
for( int i = 0; i < n; i++ )
memset( results[i], -1, result_length );
printf( "%d\n", knapsack( V, 0 ) );
return 0;
}
|