背包问题

最近看了下背包问题的算法。顺便用scala写了下简单的实现

 

问题概述：现有一个只能承受limit重量的背包，放入一些物品，物品的重量和价值在List[(Int,Int)]中，如何是背包中物品最大价值

 

 

def bag(item: List[(Int, Int)], limit: Int): Int = item match {
    case (weight, value) :: tail if (limit > 0 && limit >= weight) => 
      math.max(bag(tail, limit), value + bag(tail, limit - weight))
    case _ => 0
  }

 

 

如果是求怎么组合。List[(Int,Int,Int)]表示（id，weight，value）的列表

 

 

 def bag1(items: List[(Int, Int, Int)])(limit: Int): List[(Int, Int, Int)] = {
    def valueOf(x: List[(Int, Int, Int)]) =
      x.foldLeft(0)((sum, item) => sum + item._3)
    def greater(left: List[(Int, Int, Int)], right: List[(Int, Int, Int)]) =
      if (valueOf(left) > valueOf(right)) left else right
    items match {
      case (id, weight, value) :: tail if limit >= weight && limit > 0 =>
        greater(bag1(tail)(limit), (id, weight, value) :: bag1(tail)(limit - weight))
      case _ => Nil
    }
  }

 

效率可能不是最优（递归会消耗堆栈）的，但还算直观。