hello

I'm with problems on a dynamic programming solution for the knapsack algorithm in this problem...

I think that my implementation ignores first input pair ( price, weight ) of all test cases ( as you can see by the printf( "%d\n", carry[num][maxw] ); at the end of dp_knapsack function )...

someone can tell me why ????

Code: Select all

```
#include <stdio.h>
#define NUM 1001
#define GROUP 101
#define MW 31
int max( int x, int y )
{
return (x > y) ? x : y;
}
int dp_knapsack( const int *p, const int *wi, const int num, const int maxw )
{
int carry[NUM][MW], i, w;
for( i = 0; i <= num; i++ )
carry[i][0] = 0;
for( w = 0; w <= maxw; w++ )
carry[0][w] = 0;
for( i = 1; i <= num; i++ )
for( w = 1; w <= maxw; w++ )
{
if( wi[i] >= w )
carry[i][w] = carry[i-1][w];
else
carry[i][w] = max( carry[i-1][w], carry[i-1][w-wi[i]] + p[i] );
}
printf( "%d\n", carry[num][maxw] );
return carry[num][maxw];
}
int main()
{
int no, ng, tcases, i, total;
int price[NUM], weight[NUM], maxw;
scanf( "%d", &tcases );
while( tcases-- )
{
total = 0;
scanf( "%d", &no );
for( i = 0; i < no; i++ )
scanf( "%d %d", &price[i], &weight[i] );
scanf( "%d", &ng );
for( i = 0; i < ng; i++ )
{
scanf( "%d", &maxw );
total += dp_knapsack( price, weight, no, maxw );
}
printf( "total: %d\n", total );
}
return 0;
}
```

thanks[/quote]

"A machine can do the work of fifty ordinary men, but no machine can do the work of one extraordinary man.", Shahriar Manzoor