3

質問：m x nグリッドがあります（ 0 <= m、n <= 500）。グリッド内の各セルには k枚のコインが含まれています（kは負または0の場合もあります）。0、0から始まり、m-1、n-1で終わり、1ステップ下または1ステップ右に移動して、できるだけ多くのコインを集めることができます。k <0の場合、その特定のセルには強盗があり、そのセルに移動することはできません。隣接する8つのセルのいずれかに移動すると、 k枚のコインが奪われます。m-1、n-1に到達したときにコインはいくつありますか？

たとえば、グリッド内：

0,23,20,-32
13,14,44,-44
23,19,41,9
46,27,20,0

ans = 129（パスをたどることにより：0-13-23-46-27-20-0）

制限時間：5秒

このプログラムは動的計画法では解決できないと思います。そして、私はグラフ理論を研究していません（この問題を解決するために使用できる場合に備えて）。単純な再帰的アプローチは私が考えることができる唯一のことであり、与えられた制約の下では非効率的です。

それで、それを解決するための良いアプローチは何でしょうか？コードを投稿するだけでなく、開始方法を教えてください。グラフ理論に関連している場合は、どの定理が関係しているかを示すことが非常に役立ちます。

4

3 に答える 3

4

あなたの問題は、重み付き有向非巡回グラフの最長パス問題と呼ばれます。

（x、y）に到達したときに持つことができるコインの最大数は、次の式で与えられます。

coins(x,y) = max(coins(x-1,y), coins(x,y-1)) + change

これは漸化式です。これは、パフォーマンスのために再帰とメモ化を使用するか、反復アルゴリズムを使用することで解決できます。

反復アルゴリズムは、一度に1つの対角線でグリッドを処理することです。0,0から開始します。次に、0、1、および1,0を計算します。次に、0,2と1,1と2,0。等...

ステップ1：

 0,  ?,  ?,  ?
 ?,  ?,  ?,  ?
 ?,  ?,  ?,  ?
 ?,  ?,  ?,  ?

ステップ2：

 0, 23,  ?,  ?
13,  ?,  ?,  ?
 ?,  ?,  ?,  ?
 ?,  ?,  ?,  ?

ステップ3：

 0, 23,-33,  ?
13, 37,  ?,  ?   // 37 because of max(23,13) + 14
36,  ?,  ?,  ?
 ?,  ?,  ?,  ?

等...

このプロセスを完了すると、答えは右下隅の数字になります。

于 2012-08-26T00:08:12.487 に答える
4

このプログラムは動的計画法では解決できないと思います。

なぜだめですか？これは、動的計画法アプローチの最有力候補です。

単純な再帰的アプローチは私が考えることができる唯一のことであり、与えられた制約の下では非効率的です。

たとえば、5x5グリッドを解決する再帰的なソリューションを構築できますか？完全！それから始めて、それからあなたがすでに解決したセルのための最良の結果の配列を追加することによってそれをメモしてください。MxNその配列をすべての大きな負の値で開始し、より良い解決策が見つかったら更新します。すでにあるものよりも。セルの処理が終了したら、解をMxN配列に入れます。次に再帰的にそこに来るときは、配列で数値を確認し、値がある場合は、再帰を続行せずに返します。

メモ化されたソリューション自体はかなり単純です。アルゴリズムの前処理ステップ（隣接するセルから負の数を引く）には、より多くのコードが必要です。

int solve(int r, int c) {
    if(memo[r][c] != MIN) {
        return memo[r][c];
    }
    int res = grid[r][c];
    int a = 0, b = 0;
    if (r+1 != R) {
        a = solve(r+1, c);
    }
    if (c+1 != C) {
        b = solve(r, c+1);
    }
    res = max(res+a, res+b);
    return memo[r][c] = res;
}

これがideoneの解決策で、期待どおりに戻ります129。

于 2012-08-26T00:11:09.830 に答える
0

あなたの問題は最大フロー問題として説明される可能性があり、したがってFord-Fulkerson-Algorithmによって解決されます。

変換は次のように行われます。

  • 負のノードを削除し、隣接するセルからそれらの量を減算します。
  • 0/0がソース、m-1、n-1がシンクになります
  • 各ノードは下と右のノードに接続され、アークの容量はそのターゲットノードの値に等しくなります。
  • これで、最大フローはあなたが持つことができるコインの最大量に等しくなります

もっと簡単な解決策があるかもしれません、これは私の頭に浮かんだ最初のことです。

編集：dasblinkenlightがコメントで指摘しているように、フローは実際には複数のパスの組み合わせであるため、これは機能しません。もちろん、ここで必要なものではありません。

于 2012-08-26T00:10:09.520 に答える