0

円卓 の 周り に 円 状 に 異なる 価値 の コイン が 広げ られ て い ます . 任意の 2 つの隣接するコインのペアについて、少なくとも 1 つを選択する必要があるように、任意のコインを選択できます (両方とも選択される可能性があります)。このような状況では、選択されたコインの可能な最小値を見つける必要があります。

私は時間の複雑さを尊重しなければならないので、単純な再帰的なブルートフォースを使用する代わりに、動的プログラミングを使用して試しました。しかし、私は間違った答えを得る - 私のアルゴリズムは間違っています。

誰かがそれを動的に行うアルゴリズムを提案できれば、私は自分自身を c++ でコーディングできます。また、コインの最大数は 10^6 なので、O(n) 解が存在すると思います。

EDIT:さて、私も例を追加します。テーブルの周りのコインの値が 1,2,1,2,2 (円の中) の場合、コインの最小値は 1 番目、3 番目、4 番目 (または 5 番目) を選択すると 4 になります。

4

3 に答える 3

1

次のアルゴリズムが最善の解決策になると思います。私はあなたのコードを調べていません(申し訳ありません):

円の中のランダムな点を選択して開始します。1だとしましょう。選択された場合にどうなるかを見ていきます。

したがって、1を選択します。円を上に移動すると、2を選択するかどうかを選択できます。これは、上のブランチがコインの選択を表し、下のブランチがコインを選択しないことを表すツリーに表示できます。数字は、選択したコインの合計を表します。

   3 = 1 and 2 both selected
  /
1
  \
   1 = 1 selected, 2 not

今度はサークルを続行し、3つを選択するかどうかを選択します。これは次のような木を与えます

         6 = 1, 2 and 3 selected
       /
     3
    /  \
   /     3= 1 and 2 selected, 3 not
  /
1
  \
   \     4 = 1 and 3 selected, 2 not 
    \  /
     1 
      \
        1 = 1 selected, 2 and 3 not

今、その木で、私たちは剪定することができます!問題の説明を考えると、すべてのコインが「覆われている」ことを確認するために、どのコインが取られたかを追跡する必要があります。最後の2枚のコインが選択されなかったとしましょう。次に、制約に違反しないように次を選択する必要があることがわかります。さらに重要なことに、残りのアルゴリズムの可能性は、最後の2枚のコインの選択にのみ依存します。

最後のコイン(3)を選択したすべてのブランチを見てください。あなたは最も軽いものを保つ必要があるだけです。これらのブランチは両方とも、アルゴリズムの残りの部分で必要なものを自由に選択できます。この場合、一番上のブランチを安全に削除できます。次に、3つの可能なパスが残っています。

次に、コイン4の選択肢を列挙するとどうなるか見てみましょう。

     3      7= 1, 2 and 4 selected, 3 not
    /  \   /
   /     3
  /       \
           3 =  1 and 2 selected, 3 and 4 not 
1          8 = 1, 3 and 4 selected, 2 not 
  \       /
   \     4 
    \  /  \
     1     4 = 1 and 3 selected, 2 and 4 not 
           5 = 1 and 4 selected, 2 and 3 not
      \  /
        1 
         \
           1 = only 1 selected

今、あなたは6つの選択肢があります。ただし、3は何にも隣接していないため、最下位のブランチ(1つのみが選択されている)は無効です。それを整理して、5つのブランチを残すことができます。それらの5つのうち4つ(=これまでの最後のコイン)を選択した3つがあり、以前と同じことを行うことができます:最も安いブランチのみを保持します。これにより、ブランチの数が再び3に減ります。

再びスタートに到達するまで、サークル全体でこれを続けることができます。次に、最も安いものを選択できる3つのパスが必要です。これは、コイン1を選択することから始める場合に最適なソリューションを提供します。

これで、1が選択された場合の最適なソリューションが得られました。ただし、1を選択しないでください。選択された別のコイン(コイン2またはコイン6)に隣接している可能性があります。上記のアルゴリズムをコイン1ではなくコイン2に対して1回、コイン6に対して1回実行すると、最良の解決策が得られます。

このアプローチは、コイン1、2、または6のいずれかが選択されるという事実に依存しています。

自分のアプローチをわかりやすくしたいと思います。それはかなり長く、可能な状態(最後の2枚のコインに依存します)のみを維持し、それに取り組む状態遷移図を使用することで、より速く行うことができます。方法は上記と同じですが、よりコンパクトです)

于 2012-11-07T19:25:35.483 に答える
1

安定した開始点がないため、すべてを円形にすると動的計画法が妨げられます。

特定のコインが最良の回答に含まれることがわかっている場合は、それを出発点として使用できます。コイン 1 に再番号付けし、動的計画法を使用して、N 番目のコインを選択した場合と選択しない場合の 1..N の最適なコストを計算します。これにより、1..N+1 などの最適なコストを計算できます。

実際には、特定のコインが選択されないだろうと誰かが言った場合にも、この方法を使用できます。開始条件がわずかに異なるだけです。または、特定のコインが選択されていないことがわかっている場合は、その両側の 2 つを選択する必要があるという事実を利用することもできます。

任意のコインが選択されるかどうかのいずれかであるため、2 つの動的計画法の問題を解決することによって生成されるコストを両方の方法で確認し、コストが最も安い方を選択できます。

于 2012-11-07T19:26:39.837 に答える
0

帰納法による O(n) 提案。うーん、今ウィキを読んで、それが動的プログラミングとしてカウントされることがわかりました。実に広い用語です。以前は、動的計画法について別の理解がありました。

用語集

所々にNコインがあります。Nコインの値はa[i]です0 <= i < N。各コインは、 と のシーケンスとして表現される選択または選択解除される可能性が0あり1ます。

アルゴリズムの説明

00問題の制約に違反するため、どの場所でも無効なシーケンスです。111最適ではないため、無効でもあり、101常に優れています。

すべての場所iについて、3 つのコードの 3 つの最適な合計を順次計算します: 011011. コードは、最後の 2 つのコイン、つまり と の設定から取得されi-1ますi。したがって、変数b01b02、に最適な (最小) 合計がありますb11

確かなことから始めなければならないので、アルゴリズムを2回適用します。1 つはプレース 0 セットのコイン用で、もう 1 つはセット解除用です。

0最初に、場所を試して、直接1開始bします。b01 = a[1], b10 = a[0], b11 = a[0] + a[1]. ただし、これがセット解除する最初のコインを選択するラウンドである場合、ソリューションのみを受け入れることができb01ます。b10そのため、とに大きな数を割り当てb11ます。これらのソリューションは、次のアルゴリズム ステップですぐに削除されます。b012 番目のラウンドでは、反対のことを行います。最初のビットを設定する必要があるため、大きな数値を に割り当てます。

ステップで、 s のi場所に最適な合計が得られます。place の最適な合計である sを計算します。i-1bci

c01 = b10 + a[i]    // 101 (10 -> 01)
c10 = min(b01, b11) // 010 (01 -> 10) or 110 (11 -> 10)
c11 = b01 + a[i]    // 011 (01 -> 11)

それは次の可能性から来ています。

010 - b01 -> c10
011 - b01 -> c11
100 - invalid
101 - b10 -> c01
110 - b11 -> c10
111 - invalid

もちろん、最良の合計をbs に割り当てて各ステップを終了します。

すべてのコインを処理したら、最初の仮定と矛盾するソリューションを削除する必要があります。Bitsi-2i-1あり0、有効なシーケンスを生成する必要があります。

これは123456シーケンスの実行例です。

A. 最初のビットを想定0

1 a[1] = 2: b01 = 2, b10 = 999, b11 = 999
2 a[2] = 3: b01 = 1002, b10 = 2, b11 = 5
3 a[3] = 4: b01 = 6, b10 = 9, b11 = 1006
4 a[4] = 5: b01 = 13, b10 = 6, b11 = 11
5 a[5] = 6: b01 = 12, b10 = 13, b11 = 19

b10b01は受け入れられないので、とからより適切なものを選択しますb11。これは 12 です。

B. 最初のビットを想定1

1 a[1] = 2: b01 = 999, b10 = 1, b11 = 3
2 a[2] = 3: b01 = 4, b10 = 3, b11 = 1002
3 a[3] = 4: b01 = 7, b10 = 4, b11 = 8
4 a[4] = 5: b01 = 9, b10 = 12, b11 = 12
5 a[5] = 6: b01 = 18, b10 = 9, b11 = 15

を生成するため、 Nowb11は無効111です。ステップ A では 12、ステップ B では 9 が得られました。9 の方が優れていますb01b10これが結果です。

上記は手計算なので、間違っていたらすみません。ただし、最初のコインのセット解除では 2+4+6 を計算し、最初のコインのセットでは結果は 1+3+5 でした。正しいようです。

于 2012-11-07T20:40:23.657 に答える