1

私はプログラミングフォーラムでこの質問を見つけました：

それぞれ一定量のリンゴを含むN*M細胞で構成される表が示されています。左上隅から始めます。各ステップで、1つのセルを下または右に移動できます。左上隅から右下隅に移動する場合は、収集できるリンゴの最大数を見つけるためのアルゴリズムを設計します。

私は3つの異なる複雑さを考えました[時間と空間の観点から]：

アプローチ1[最速]： 

for(j=1,i=0;j<column;j++)
    apple[i][j]=apple[i][j-1]+apple[i][j];
for(i=1,j=0;i<row;i++)
    apple[i][j]=apple[i-1][j]+apple[i][j];

for(i=1;i<row;i++)
{
    for(j=1;j<column;j++)
    {
        if(apple[i][j-1]>=apple[i-1][j])
            apple[i][j]=apple[i][j]+apple[i][j-1];
        else
            apple[i][j]=apple[i][j]+apple[i-1][j];
    }
}
printf("\n maximum apple u can pick=%d",apple[row-1][column-1]);

アプローチ2：

結果は、最初はすべてのスロットが0である一時アレイです。 

int getMax(int i, int j)
{
    if( (i<ROW) && (j<COL) )
    {
        if( result[i][j] != 0 )
            return result[i][j];
        else
        {
            int right = getMax(i, j+1);
            int down = getMax(i+1, j);

            result[i][j] = ( (right>down) ? right : down )+apples[i][j];
            return result[i][j];
        }
    }
    else
        return 0;
}

アプローチ3[使用される最小スペース]：

一時配列は使用しません。 

int getMax(int i, int j)
{
    if( (i<M) && (j<N) )
    {
            int right = getMax(i, j+1);
            int down = getMax(i+1, j);
            return apples[i][j]+(right>down?right:down);
    }
    else
        return 0;
}

この問題を解決するための最良の方法を知りたいですか？

4

3 に答える 3

3

アプローチ1と2の間にほとんど違いはありません。アプローチ2は逆方向に進むため、アプローチ2が使用する再帰のスタックを必要としないため、アプローチ1の方がおそらく少し優れています。

アプローチ3は指数関数的な時間計算量を持っているため、complexitx O（rows * columns）を持つ他の2つよりもはるかに悪いです。

O（max {rows、columns}）の追加スペースのみを使用するために、対角線に沿って進むアプローチ1の変形を作成できます。

于 2012-07-23T14:06:31.960 に答える
0

時間的には、再帰関数がないため、ソリューション1が最適です。再帰関数の呼び出しには時間がかかります

于 2012-07-23T14:08:15.017 に答える
0

最初のアプローチの改善

一時配列をNxMにする必要が本当にありますか？

いいえ。

最初の2次元配列にN列とM行がある場合、長さMの1次元配列でこれを解決できます。

方法

最初のアプローチでは、すべての小計を保存しますが、実際には、次の列に移動するときに、左上のセルのアップル値を知る必要があるだけです。それを決定したら、それらの前のセルを二度と見ることはありません。

解決策は、次の列からやり直すときに古い値を上書きすることです。

コードは次のようになります（私は実際にはCプログラマーではないので、我慢してください）。

コード

int getMax()
{
    //apple[][] is the original apple array
    //N is # of columns of apple[][]
    //M is # of rows of apple[][]
    //temp[] is initialized to zeroes, and has length M

    for (int currentCol = 0; currentCol < N; currentCol++)
    {
        temp[0] += apple[currentCol][0]; //Nothing above top row

        for (int i = 1; i < M; i++)
        {
            int applesToLeft = temp[i];
            int applesAbove = temp[i-1];

            if (applesToLeft > applesAbove)
            {
                temp[i] = applesToLeft + apple[currentCol][i];
            }
            else
            {
                temp[i] = applesAbove + apple[currentCol][i];
            }
        }
    }

    return temp[M - 1];
}

注：applesToLeftとapplesAboveの値を実際にローカル変数に格納する理由はありません。自由に？を使用してください。：割り当ての構文。

また、行よりも列が少ない場合は、これを回転して、1次元配列の長さが短くなるようにする必要があります。

このようにすることで、メモリを節約できるため、最初のアプローチを直接改善できます。さらに、同じ1次元配列を反復処理すると、キャッシュに非常に役立ちます。

別のアプローチを使用する理由は1つしか考えられません。

マルチスレッド

この問題に対してマルチスレッドの利点を得るには、2番目のアプローチがちょうどいいです。

2番目のアプローチでは、メモを使用して中間結果を保存します。

メモをスレッドセーフにすると（ロックするか、ロックフリーのハッシュセットを使用して）、複数のスレッドを開始して、右下隅の答えを取得しようとすることができます。

[//編集：実際には、配列へのintの割り当ては不可分操作であるため、ロックする必要はまったくないと思います]。

getMaxを呼び出すたびに、左側のgetMaxを実行するかgetMaxを超えるかをランダムに選択します。

これは、各スレッドが問題の異なる部分で機能し、メモがあるため、別のスレッドがすでに行った作業を繰り返さないことを意味します。

于 2012-07-26T01:12:49.507 に答える