¿Por qué esta solución de DP al problema de mochila 0/1 no da la salida correcta con GCC?

Question

#include<stdio.h> 

int max(int a,int b) 
{ 
    if(a>b) 
     return a; 
    else 
     return b; 
} 

void knapsack(int m,int n,int w[],int p[]) 
{ 
    int v[10][10],x[10],i,j; 
    for(i=0;i<=n;i++) 
    { 
     for(j=0;j<=m;j++) 
     { 
      if(j==0||i==0) 
       v[i][j]=0; 
      if(j-w[i]<0) 
       v[i][j]=v[i-1][j]; 
      else 
       v[i][j]=max(v[i-1][j],v[i-1][j-w[i]]+p[i]); 
     } 
    } 
    for(i=0;i<=n;i++) 
    { 
     for(j=0;j<=m;j++) 
      printf("%d\t",v[i][j]); 
     printf("\n"); 
    } 
    printf("THE OPTIMAL SOLUTION IS:%d",v[n][m]); 
    for(i=1;i<=n;i++) 
     x[i]=0; 
    i=n; 
    j=m; 
    while(i>0 && j>0) 
    { 
     if(v[i][j]!=v[i-1][j]) 
     { 
      x[i]=1; 
      j=j-w[i]; 
     } 
     i--; 
    } 
    printf("THE OPTIMAL SET OF WEIGHTS IS:"); 
    for(i=1;i<=n;i++) 
     if(x[i]==1) 
      printf("%d\t",i); 
    printf("\n"); 
} 

int main() 
{ 
    int w[10],p[10],i,m,n; 
    printf("ENTER THE NUMBER OF ITEMS:"); 
    scanf("%d",&n); 
    printf("ENTER THE WEIGHTS OF THE ITEMS:"); 
    for(i=1;i<=n;i++) 
     scanf("%d",&w[i]); 
    printf("ENTER THE PROFITS OF THE ITEMS:"); 
    for(i=1;i<=n;i++) 
     scanf("%d",&p[i]); 
    printf("ENTER THE CAPACITY OF KNAPSACK:"); 
    scanf("%d",&m); 
    knapsack(m,n,w,p); 
    return 0; 
} 

muestra de salida:

chaitanya@chaitanya-laptop:~/Desktop/My prog$ ./a.out 

ENTER THE NUMBER OF ITEMS:5 

ENTER THE WEIGHTS OF THE ITEMS:3 
2 
1 
2 
3 

ENTER THE PROFITS OF THE ITEMS:2 
3 
2 
3 
2 

ENTER THE CAPACITY OF KNAPSACK: 8 

0 -72 -1080992920 -72 0 1 -1080993280 0 13403040  
0 -72 -1080992920 2 0 1 -70 2 13403040  
0 -72 3 2 0 5 3 4 13403040  
0 2 3 5 4 5 7 5 13403040  
0 2 3 5 6 8 7 8 13403040  
0 2 3 5 6 8 7 8 13403040  

THE OPTIMAL SOLUTION IS:13403040 

THE OPTIMAL SET OF WEIGHTS IS: 

Nota: El mismo programa produce una salida legítima para la misma entrada cuando se compila en el compilador TurboC. (Si alguien está viendo esto en 2015 - ¡deje de usar TurboC!)

Eso me lleva a pensar que no estoy cumpliendo con los estándares de C. ¿Es eso así?

Answer 1

Al inicializar w está utilizando la indexación basada en 1:

for(i=1;i<=n;i++) 
     scanf("%d",&w[i]); 

Pero cuando se accede a él, está utilizando la indexación basada en 0.

for(i=0;i<=n;i++) 
{ 
    for(j=0;j<=m;j++) 
    { 
     if(j==0||i==0) 
      v[i][j]=0; 
     if(j-w[i]<0) // This line accesses w[0] when i is 0. Missing an else? 
      v[i][j]=v[i-1][j]; 
     else 
      v[i][j]=max(v[i-1][j],v[i-1][j-w[i]]+p[i]); 
    } 
} 

En C, las matrices usan indización basada en 0. Cambie su código para usar la indexación basada en 0 de manera consistente.

Además, debe verificar el valor de retorno de scanf de lo contrario, la entrada no válida dará resultados extraños en lugar de un error.

for (i=0; i < n; i++) { 
    if (scanf("%d", &w[i]) != 1) { 
     return EXIT_FAILURE; // Handle the error appropriately. 
    } 
} 

Answer 2

puede estar con mismo código .. incluyendo < limits.h> funcionará .. simplemente hacer elemento indexado a 0 ª -INFINITY por (nombre de la matriz) [0] = - INT_MAX.