Segmentation fault in C with only certain inputs

Question

Okay, so I'm trying to solve the Knapsack problem.

On small input cases the program runs with no problem and provides the optimal solution, however when the input size is large, or rather the numbers in the input file become large, the program gives me a segmentation fault. I don't quite get why is this happening since the max value of INT exceeds any of these numbers too.

Here's my code.

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

It runs perfectly for this input http://spark-public.s3.amazonaws.com/algo2/datasets/knapsack1.txt

But when the input size is the one given in the link, it provides a seg fault http://spark-public.s3.amazonaws.com/algo2/datasets/knapsack2.txt Thanks for the help!

You may want to compile your program with debug symbols and attach a debugger. It will tell you exactly where your program segfaults. — Sjoerd, Jan 04 '13 at 10:15
How are you doing this? `int value[n+1],weight[n+1];` This shouldn't even compile. — sgarizvi, Jan 04 '13 at 10:18
@sgar91 that looks like perfectly valid C99. Drag yourself out of the eighties! — ams, Jan 04 '13 at 10:18
@ams... Actually I use C++. Also neither the question is tagged with `C99` nor it is mentioned in the question. — sgarizvi, Jan 04 '13 at 10:20
[Do not cast the return of malloc](http://stackoverflow.com/questions/605845/) — Eregrith, Jan 04 '13 at 10:20
@sgar91 The question *is* tagged C, and the official C standard is now C11. C89 is dead, yet not forgotten. :) — ams, Jan 04 '13 at 10:22

amit · Accepted Answer · 2013-01-04T10:21:39.770

When allocating the arrays for the 2nd dimension you do:

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

It should be n+1 instead of W+1 in the loop. You should iterate over the "items" dimensions and allocate "weight" dimension.

The solution will work perfectly for n <= W, but for larger number of items (W < n) - you will get undefined behavior, because you are trying to access A[n][0] at some point, but you did not allocate the array for the nth item.

So basically - you need to change the initialization of the 2nd dimension to:

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

Segmentation fault in C with only certain inputs

1 Answers1