分段故障，只有某些输入

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