2

セルタワーについて質問があります。n 個の町があります。いくつかの町にセルタワーを建設したいと考えています。各基地局は、それ自体と隣接する基地局をカバーできます。各町には、セルタワーを建設するためのコストがあります。すべての町をカバーするセル タワーを建設するための最小コストを調べたいと考えています。

例えば、

(1)

タウン 1 2 3

COST 5 1 2 タウン 2 にセル タワーを建設することを選択します。コストは 1 です。

(2)

タウン 1 2 3 4

COST 5 1 2 3 タウン 2/3 にセル タワーを建設することを選択します。コストは 1+2=3 です。

(3)

タウン 1 2 3 4

コスト 5 1 3 2

タウン 2/4 にセル タワーを建設することを選択します。コストは 1+2=3 です。

動的計画法のアルゴリズムです。どうすれば解決できますか？

ありがとうリン

4

1 に答える 1

1

次の行のいずれかを使用します。

f(0,_) = 0
f(1,true) = 0
f(1,false) = cost[1]
f(x,true) = min{ f(x-1,true) + cost[x], f(x-1,false) }
f(x,false) = min { f(x-1,true) + cost[x], f(x-2,true) + cost[x-1]}

アイデアは次のとおりです。

xは現在見ている都市の数であり、この都市がすでに (左からの都市によって) カバーされている場合、ブール値は true です。

  • f(0,_)は空の基本節です。何もカバーする必要はありません。
  • f(1,false)は都市 1 がカバーされていない基地なので、そこにタワーを配置する必要がありf(1,true)ます。 は都市 1 がカバーされている基地なので、タワーは必要なく、完了です。
  • f(x,true)都市 x はすでにカバーされているので、そこにタワーを置いて次の都市 [これもカバーされている - f(x-1,true)] に進むか、そこにタワーを置かず、次の都市はカバーされていない [ f(x-1,false)]
  • f(x,false)は都市 x がカバーされていない場合なので、基本的に 2 つの選択肢があります。または、そこにタワーを配置してから に進みf(x-1,true)ます。または、次の都市 (x-1) に塔を設置してから、f(x-2,true)

から始めてf(x,false)、xは最後の都市であり、最小の解が得られます。
この再帰式を DP に簡単に変更できることは簡単にわかります。

于 2013-08-09T23:51:43.420 に答える