Tại sao giải pháp DP này đối với vấn đề Knapsack 0/1 không cho kết quả chính xác với 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; 
} 

MẪU OUTPUT:

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: 

Lưu ý: Chương trình cùng tạo ra một sản lượng hợp pháp cho các đầu vào tương tự khi biên soạn trong trình biên dịch TurboC. (Nếu bất kỳ ai nhìn thấy điều này trong năm 2015 - ngừng sử dụng TurboC!)

Vì vậy, điều đó dẫn tôi tin rằng tôi không tuân thủ các tiêu chuẩn C. Là vậy sao?

Answer 1

Khi bạn khởi w bạn đang sử dụng chỉ mục 1-based:

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

Nhưng khi bạn truy cập vào nó, bạn đang sử dụng 0 dựa trên lập chỉ mục.

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

Trong mảng C sử dụng lập chỉ mục dựa trên 0. Thay đổi mã của bạn để sử dụng chỉ mục dựa trên 0 một cách nhất quán.

Ngoài ra, bạn nên kiểm tra giá trị trả lại của scanf cách nhập không hợp lệ sẽ cho kết quả lạ thay vì lỗi.

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

Answer 2

có thể có cùng một mã .. bao gồm < limits.h> sẽ làm việc .. chỉ cần đảm yếu tố được lập chỉ mục 0 đến vô cực (tên mảng) [0] = - INT_MAX.