2011-11-20 10 views
7
#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: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?

[email protected]:~/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?

+1

Hãy thử sử dụng trình gỡ lỗi như 'gdb' và biên dịch chương trình của bạn bằng' -Wall -g' –

Trả lời

10

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. 
    } 
} 
+0

tôi biết rằng các mảng được lập chỉ mục 0 nhưng trong trường hợp này tôi không truy cập w [0] ở bất kỳ đâu. –

+0

có trong một kịch bản lý tưởng tôi nên kiểm tra các điều kiện có thể gây ra vỡ nhưng rõ ràng đối với đầu vào đã cho không phải điểm nào mà bạn nói đến đều gây ra lỗi. –

+2

@guy: Vâng, đúng vậy. Bên trong vòng lặp bên trong gán cho 'v [i] [j]', lần đầu tiên. –

0

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.