用Scala动态规划求解CodeChef混料
我正在尝试使用scala解决下面的编解码问题。关于这一问题的说明如下：
哈利波特面前有n个混血，排成一排。每种混合物都有100种不同的颜色(颜色的数字从0到99)。 他想把所有这些混合物混合在一起。在每一步，他将采取两种混合物站在一起，并将它们混合在一起，并将产生的混合物放在他们的位置。 当混合两种颜色a和b时，产生的混合物将具有颜色(a+b) mod 100。 而且，在这个过程中会有一些烟雾。混合两种颜色a和b时产生的烟雾量为a*b。 找出哈利在混合所有混合物时所能产生的最小烟雾量。
提供的样本答复如下：
输入： 2 18 19 3 40 60 20 输出： 342 2400 在第二个测试用例中，有两种可能性： 先混合40和60 (烟雾: 2400)，再混合0和20 (烟雾: 0)；总烟量为2400，先混合60和20 (烟雾: 1200)，再混合40和80 (烟雾: 3200)；总烟雾量为4400。 第一种方案是正确的方法，因为它将产生的烟雾量降到最低。
我知道这可以使用动态规划来解决，但我在处理这个问题和用scala表示算法时遇到了困难。
下面是我对这个问题的思考，在某种查找结构(Array，Map和Tuple(Int，Int)作为键)中，存储所有用于混合两种颜色的计算值
这可以通过以下伪代码来实现：
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一旦计算出所有的初始颜色，现在我们需要考虑混合颜色的顺序，同时考虑到产生的烟雾。这就是我遇到麻烦的地方。我撞到了一面墙，试图制定一个子结构，这将提供最低限度的烟雾产生。
在这里得到一些指导将是很好的。
谢谢
回答 2
Stack Overflow用户
发布于 2012-04-27 14:27:40
我编写了以下动态编程解决方案。它也可以作为要旨使用。
/** 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)Stack Overflow用户
发布于 2012-04-27 17:12:49
我不认为动态编程和它有多大关系。我认为这是一个图问题，用广度优先搜索解决。一个直接的最短路径问题。
https://stackoverflow.com/questions/10350338
复制相似问题
腾讯云开发者
