0/1 Knapsack समस्या के लिए यह डीपी समाधान क्यों जीसीसी के साथ सही आउटपुट नहीं देता है?

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

नमूना उत्पादन:

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: 

नोट: एक ही कार्यक्रम जब TurboC संकलक में संकलित एक ही इनपुट के लिए एक वैध उत्पादन पैदा करता है। (अगर कोई 2015 में यह देख रहा है - TurboC का उपयोग बंद!)

तो है कि मुझे विश्वास है कि मैं सी मानकों का पालन नहीं कर रहा हूँ। ऐसा क्या?

Answer 1

आप प्रारंभ जब डब्ल्यू आप 1 आधारित अनुक्रमण का उपयोग कर रहे हैं:

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

लेकिन जब आप उस तक पहुँच, आप 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]); 
    } 
} 

सी एरे में 0-आधारित अनुक्रमण का उपयोग करें। लगातार 0-आधारित अनुक्रमण का उपयोग करने के लिए अपना कोड बदलें।

इसके अलावा, आप scanf अन्यथा अमान्य इनपुट के वापसी मान की जाँच के बजाय अजीब परिणाम एक त्रुटि दे देंगे चाहिए।

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

Answer 2

.. एक ही कोड के साथ हो सकता है सहित < limits.h> काम करेंगे .. बस (सरणी नाम) द्वारा -infinity को 0 अनुक्रमित तत्व बनाने [0] = - INT_MAX।