C中的分段故障仅包含某些输入

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

但是当输入大小是链接中给出的大小时,它会提供一个seg错误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项目分配数组.

基本上 - 您需要将第二维的初始化更改为:

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