2

scalaを使用して、次のcodechefの問題を解決しようとしています。問題文は以下の通り。

ハリー・ポッターの前に n 個の混合物が一列に並んでいます。各混合物には、100 の異なる色 (色には 0 から 99 までの数字があります) のいずれかがあります。

彼は、これらすべての混合物を混ぜ合わせたいと考えています。各ステップで、彼は隣り合った 2 つの混合物を取り、それらを一緒に混合し、得られた混合物をその場所に置きます。

色 a と b の 2 つの混合物を混合すると、結果の混合物は色 (a+b) mod 100 になります。

また、途中で煙が出ます。色 a と b の 2 つの混合物を混合したときに生成される煙の量は、a*b です。

すべての混合物を混ぜ合わせたときに、ハリーが得ることができる煙の最小量を調べてください。

提供される回答例は次のとおりです。

入力：

2 
18 
19 
3
40
60
20

出力：

342
2400

2 番目のテスト ケースでは、次の 2 つの可能性があります。

first mix 40 and 60 (smoke: 2400), getting 0, then mix 0 and 20 (smoke: 0); total amount of smoke is 2400
first mix 60 and 20 (smoke: 1200), getting 80, then mix 40 and 80 (smoke: 3200); total amount of smoke is 4400

最初のシナリオは、生成される煙の量を最小限に抑えるため、正しいアプローチです。

これは動的プログラミングを使用して解決できることは理解していますが、この問題に取り組み、アルゴリズムを scala で表現するのに問題があります。

これが私がこの問題についてどのように考えているかです。ある種のルックアップ構造（配列、キーとしてTuple（Int、Int）を使用したマップ）で、2つの色を混合するために計算されたすべての値を保存します

これは、次の疑似コードで実現できます。

for(colors1<-1 through n)
   for(colors2<-k through n)
      if(color1 != color2)
          //Check if color1,color2 combination exists as (color1,color2) or (color2,color1)    
          Map(color1,color2) = (color1+color2)%100

すべての初期色が計算されたら、生成された煙を考慮して、色を混合する順序を考慮する必要があります。これは私が問題を抱えているところです。生成される煙を最小限に抑えるサブ構造を策定しようとして、壁にぶつかっています。

ここでいくつかのガイダンスを得るのは素晴らしいことです。

ありがとう

4

2 に答える 2

1

次の動的計画法ソリューションを作成しました。gistとしても利用できます。

/** Find the minimum amount of smoke (second) and resulting color (first) 
    by splitting the sequence at every possible position,
    given `lookup` contains the best mix for subsequence. */
def minSmokeMixtureSingle(s: Seq[Int], lookup: Map[Seq[Int],(Int,Int)])
  : (Int,Int) = 
    if(s.size == 1)
        (s(0),0)
    else if(s.size == 2)
        mix(s(0),s(1))
    else {
        val splits = (1 to (s.size - 1)).map(s.splitAt)
        val mixes = splits.map{ case (s1,s2) => 
            val (c1,sm1) = lookup(s1)
            val (c2,sm2) = lookup(s2)
            val (newColor,newSmoke) = mix(c1,c2)
            (newColor, newSmoke + sm1 + sm2)
        }
        mixes.minBy(_._2)
    }

def mix(m1: Int, m2: Int): (Int,Int) = ((m1+m2) % 100, m1*m2)

def minSmokeMixture(s: Seq[Int]) = {
    //create the mixture sequences with increasing length
    val windows = for(windowSize <- 1 to s.size;
        window <- s.sliding(windowSize) ) yield window
    //go over the sequences and compute the lookup-table
    val lookup = windows.foldLeft(Map.empty[Seq[Int],(Int,Int)]){
        case (lu,seq) => lu + (seq -> minSmokeMixtureSingle(seq,lu))
    }
    //simply lookup the result
    lookup(s)
}

println(minSmokeMixture(Seq(18, 19)))
println(minSmokeMixture(Seq(40, 60, 20)))

これは確かにスタイルの面で改善することができます.

与えられた例に対して正しい出力を生成します (2 番目の数値は煙、最初の数値は最終的な色です)。

(37,342)
(20,2400)
于 2012-04-27T14:27:40.140 に答える
0

動的プログラミングはあまり関係ないと思います。これはグラフの問題であり、幅優先探索で解決されると思います。直線最短経路問題。

于 2012-04-27T17:12:49.503 に答える