Scala 中带记忆的背包解决方案

Question

您好，我正在尝试使用 Memoization 在 Scala 中实现 Knapsack 解决方案。这是没有记忆的代码

// knapsack = maxWeight: Int, weights: List[Int], values: List[Int]
val knapsack: ((Int, List[Int], List[Int]) => Int) = Memo {
     case (0, _, _) | (_, Nil, _) | (_, _, Nil) => 0
     case (weight, headWt :: tailWts, _ :: tailVals) if headWt > weight => 
                                       knapsack(weight, tailWts, tailVals)
     case (weight, headWt :: tailWts, headVal :: tailVals) => math.max(
                                       headVal+knapsack(weight-headWt, tailWts, tailVals),
                                       knapsack(weight-headWt, tailWts, tailVals))  
}

println(knapsack(50, weights.sortBy(-_), values.sortBy(-_)))

备忘录的定义如下：

case class Memo[A,B](f: A=>B) extends mutable.HashMap[A,B]{
     override def apply(a: A):B = {
          getOrElseUpdate(a, f(a))
     }
}

但是，我遇到编译时错误：

  Type mismatch, expected: List[Int], actual: List[Any]

如果我删除备忘录，它会正常工作。

谢谢。

Answer 1

我不确定您在哪一行收到错误

Type mismatch, expected: List[Int], actual: List[Any]

如果我将 knapsack 的类型更改为 (((Int, List[Int], List[Int])) => Int)，即 Function1 从元组 (Int, List[Int], List[Int]) 更改为 Int，您的代码带有 Memo为我编译没有任何错误。

// knapsack = maxWeight: Int, weights: List[Int], values: List[Int]
val knapsack: (((Int, List[Int], List[Int])) => Int) = Memo {
  case (0, _, _) | (_, Nil, _) | (_, _, Nil) => 0
  case (weight, headWt :: tailWts, _ :: tailVals) if headWt > weight =>
    knapsack(weight, tailWts, tailVals)
  case (weight, headWt :: tailWts, headVal :: tailVals) => math.max(
    headVal + knapsack(weight - headWt, tailWts, tailVals),
    knapsack(weight - headWt, tailWts, tailVals))
}

val weights: List[Int] = List(10, 20, 30)
val values: List[Int] = List(2, 3, 4)
println(knapsack(50, weights.sortBy(-_), values.sortBy(-_)))

产生预期的

7

Scala 中带记忆的背包解决方案

Knapsack Solution in Scala With Memoization

scala

scalaz