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

我不知道哪个行你得到你的错误

类型不匹配，预计：列表[INT]，实际：列表[任何]

如果我改变的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(-_))) 

产生预期