使用Scala動態編程來解決CodeChef的混合問題

我正在嘗試使用scala解決以下codechef problem問題。這個問題的陳述如下：使用Scala動態編程來解決CodeChef的混合問題

哈利波特在他面前有n個混合物，排列成一排。每種混合物都有100種不同顏色之一（顏色的編號從0到 99）。

他想混合所有這些混合物。在每個步驟中，他要去取兩種彼此相鄰的混合物並將它們混合在一起，並將所得到的混合物置於其位置。

當混合的顏色a和b兩種混合物，將得到的混合物將具有的顏色（A + B）模100

而且，存在將在過程中的一些煙霧。混合兩種顏色a和b的混合物時產生的煙霧量爲a * b。

找出Harry將混合在一起的最小煙霧量是多少。

提供示例答案如下：

輸入：
2 
18 
19 
3 
40 
60 
20 
輸出：
342 
2400 
在第二個試驗的情況下，有兩種可能性：
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中表達算法。

以下是我一直在思考這個問題，在某種查找結構中（陣，地圖與元組（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

一旦所有的初始顏色已經被計算，現在我們需要考慮我們混淆了顏色要考慮到所產生的煙霧中的順序。這是我遇到問題的地方。我試圖制定能夠提供最低煙霧的子結構。

這將是很好的一些指導在這裏。

謝謝

來源

2012-04-27 sc_ray

連我都開始覺得與更頻繁地使用循環與可變數據結構的命令式語言相比，在斯卡拉方面建模爲動態規劃問題是有點難度。 – 2015-01-07 20:20:19

我寫了下面的動態編程解決方案。它也可以作爲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)

來源

2012-04-27 14:27:40 ziggystar

非常感謝。我仍然在醞釀一些階語法，但是這在我看來，解決這個問題的正確方法。 – 2012-04-27 18:32:55

@sc_ray隨意在這裏提問。代碼中有很多事情要做。 – ziggystar 2012-04-27 21:01:00

我不認爲動態預設電臺有很大關係吧。我認爲這是一個圖形問題，用廣度優先搜索來解決。直接shortest path的問題。

來源

2012-04-27 17:12:49

我在這裏看不到圖搜索。那麼你得到的複雜性是什麼？我的算法至多有'O（n^3）'。我懶得去思考它是否更低。 – ziggystar 2012-04-27 17:21:39

@ziggystar'O（| E | + | V |登錄| V |）'，所以我們需要知道有多少個頂點可以有。 sortest路徑最多可以有'n - 1'個頂點，但我認爲頂點的實際數量是指數。邊的數量由頂點數限制。 – 2012-04-27 17:32:51

使用Scala動態編程來解決CodeChef的混合問題

回答

相關問題