0

さて、ナップザックの問題を解決しようとしています。

入力が小さい場合、プログラムは問題なく実行され、最適なソリューションが提供されますが、入力サイズが大きい場合、または入力ファイル内の数値が大きくなると、プログラムはセグメンテーション違反を引き起こします。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が提供 されます 助けてくれてありがとう!

4

1 に答える 1

6

2 番目の次元に配列を割り当てるときは、次のようにします。

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

n+1代わりにW+1ループする必要があります。「アイテム」ディメンションを反復処理し、「重量」ディメンションを割り当てる必要があります。

解決策は完全に機能しますn <= Wが、アイテムの数が多いW < n場合（ ）-ある時点でアクセスしようとしているが、 th アイテムに配列を割り当てていないため、未定義の動作が発生します。A[n][0]n

したがって、基本的に-2次元の初期化を次のように変更する必要があります。

for(i=0;i<n+1;i++)
     A[i]=(int *)malloc(sizeof(int)*(W+1));
于 2013-01-04T10:15:31.660 に答える