分段故障，只有某些輸入

Question

好了，所以我試圖解決的揹包問題。

在小的輸入情況下，程序沒有問題的運行，並提供最佳的解決方案，但是當輸入尺寸較大，或者說在變大輸入文件中的數字，該計劃給了我一個分段錯誤。我不明白爲什麼會發生這種情況，因爲INT的最大值也超過了這些數字中的任何一個。

這是我的代碼。

#include<stdio.h> 
    #include<stdlib.h> 
    int main(void) 
    { 
     int W,n,i,j,k ; 
     scanf("%d %d",&W,&n); // capacity of knapsack and number of total items 
     int value[n+1],weight[n+1]; 
     int** A; 
     A = (int **)malloc((n+1)*sizeof(int*)); 
     for(i=0;i<W+1;i++) 
      A[i]=(int *)malloc(sizeof(int)*(W+1)); 
     for(i=1;i<n+1;i++) 
     { 
      scanf("%d %d",&value[i],&weight[i]); //taking value and weight of each item 
     } 
     for(i=0;i<W+1;i++) 
      A[0][i]=0; 
     for(i=0;i<n+1;i++) 
      A[i][0]=0; 
     for(i=1;i<n+1;i++) 
     { 
      for(j=1;j<W+1;j++) 
      { 
       if(j-weight[i]<0) 
       { 
        A[1][j]=A[0][j]; 
       } 
       else 
       { 
        if(A[0][j]>A[0][j-weight[i]]+value[i]) 
         A[1][j]=A[0][j]; 
        else 
         A[1][j]=A[0][j-weight[i]]+value[i]; 
       } 
      } 
      for(k=0;k<W+1;k++) 
       A[0][k]=A[1][k]; 
     } 
     int max=0; 
     i=1; 
     for(i=0;i<2;i++) 
      for(j=0;j<W+1;j++) 
      { 
       if(A[i][j]>max) 
        max=A[i][j]; 
      } 
     printf("%d\n",max); 
     return(0); 
    } 

它運行完美此輸入http://spark-public.s3.amazonaws.com/algo2/datasets/knapsack1.txt

但是當輸入的大小是在一個給出的鏈接，它提供了一個賽格故障http://spark-public.s3.amazonaws.com/algo2/datasets/knapsack2.txt 感謝您的幫助！

Answer 1

當分配的數組爲你做的第二維：

for(i=0;i<W+1;i++) 
    A[i]=(int *)malloc(sizeof(int)*(W+1)); 

應該n+1而不是W+1的循環。您應該遍歷「項目」維度並分配「權重」維度。

該解決方案將很好地工作爲n <= W，但對於更大數量的項目（W < n） - 你會得到未定義行爲，因爲你想在某個時候訪問A[n][0]，但你沒有分配的數組中n第th項。

所以基本上 - 你需要在第二維的初始化更改爲：

for(i=0;i<n+1;i++) 
    A[i]=(int *)malloc(sizeof(int)*(W+1));