algorithm - 使用 Scala 的动态编程来解决来自 CodeChef 的 Mixture

Question

我正在尝试解决以下问题 codechef problem使用标度。问题陈述如下:

Harry Potter has n mixtures in front of him, arranged in a row. Each mixture has one of 100 different colors (colors have numbers from 0 to 99).

He wants to mix all these mixtures together. At each step, he is going to take two mixtures that stand next to each other and mix them together, and put the resulting mixture in their place.

When mixing two mixtures of colors a and b, the resulting mixture will have the color (a+b) mod 100.

Also, there will be some smoke in the process. The amount of smoke generated when mixing two mixtures of colors a and b is a*b.

Find out what is the minimum amount of smoke that Harry can get when mixing all the mixtures together.

提供的示例答案如下:

Input:

2 
18 
19 
3
40
60
20

Output:

342
2400

In the second test case, there are two possibilities:

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

The first scenario is the correct approach since it minimizes the amount of smoke produced.

我知道这可以使用动态规划来解决，但我在处理这个问题和用 Scala 表达算法时遇到了问题。

这就是我对这个问题的思考方式，在某种查找结构中(数组，以元组(Int，Int)为键的 map )存储混合两种颜色的所有计算值

这可以通过以下伪代码来完成:

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

计算完所有初始颜色后，现在我们需要考虑在考虑产生的烟雾的情况下混合颜色的顺序。这是我遇到问题的地方。我在尝试构建能够产生最少烟雾的子结构时碰壁了。

如果能在这里得到一些指导会很棒。

谢谢

Answer 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)))

这当然可以在样式方面进行改进。

它为给定的示例生成正确的输出(第二个数字是烟雾，第一个是最终颜色):

(37,342)
(20,2400)