0

我正在玩 Knapsack（没有真正好的理由，只是想去除一些锈迹）并想用我最喜欢的语言实现它

（请不要笑，大学已经有一段时间了，我对 Scala 还很陌生）

这是我的第一次运行（它返回正确的解决方案，但我认为它远非最佳）：

import scala.collection.mutable.HashMap

object Main {
  def main(args: Array[String]) {
    val weights = List(23, 31, 29, 44, 53, 38, 63, 85, 89, 82)
    val values = List(92, 57, 49, 68, 60, 43, 67, 84, 87, 72)
    val wv = weights zip values
    val solver = new KnapSackSolver()
    solver.solve(wv, 165) 

  }

  class KnapSackSolver() {

    var numberOfIterations = 0
    type Item = (Int, Int)
    type Items = List[Item]

    val cache = new HashMap[(Items, Int), Items]()

    def sackValue(s: Items) = if (s.isEmpty) 0 else s.map(_._2).sum

    def solve(wv: Items, capacity: Int) = {
      numberOfIterations = 0
      val solution = knapsack(wv, capacity)

      println(s"""|Solution: $solution
                  |Value: ${sackValue(solution)}
                  |Number of iterations: $numberOfIterations
      """.stripMargin)

      solution 
    }

    private[this] def knapsack(wv: Items, capacity: Int): Items = {
      numberOfIterations +=1
      val cacheKey = (wv, capacity)
      if (cache.contains(cacheKey)) {
        return cache(cacheKey) //I know, I wrote a return, just wanted an early exit
      }

      if (capacity <= 0 || wv.isEmpty) {
        Nil
      } else if (wv.head._1 > capacity) {
        knapsack(wv.tail, capacity)
      } else {
        val sackNotTakingCurrent = knapsack(wv.tail, capacity)
        val sackTakingCurrent = knapsack(wv.tail, capacity - wv.head._1) :+ wv.head

        val notTakingCurrentValue = sackValue(sackNotTakingCurrent)
        val takingCurrentValue = sackValue(sackTakingCurrent)
        val ret =
          if (notTakingCurrentValue >= takingCurrentValue) sackNotTakingCurrent
          else sackTakingCurrent

        cache(cacheKey) = ret
        ret
      }
    }
  }
}

问题

我幼稚的“缓存”似乎不够好（565 与 534 次迭代），但我不知道如何改进它，我感觉涉及填充大小 itemsXweight 的矩阵，但不知道从哪里开始。

换句话说 - 这是最佳解决方案吗？对我来说感觉非常指数，但如果我说我理解伪多项式的真正含义，我会撒谎......如果这不是最佳解决方案，我怀疑它不是，我错过了什么？

4

2 回答 2

0

这是可以解释您概念的 scala 代码（它没有在 REPL 上测试，但会为您提供如何处理背包问题的直觉）

def KnapsackSolver(Weights: List[Int],Values: List[Int],Capacity: Int): (Int,List[Int]) {

    val cache = new HashMap((Int,Int),Int)()

    def solve(W: List[Int],V: List[Int],C: Int) : Int  = {

       if(W.Length<1)
          0
       else {

         val currV = V.head
         val currW = W.head
         val Key1 = (W.length-1,C)
         val Key2 = (W.length-1,C-currW)
         val sum1 = 
            if(cache.containsKey(Key1)) 
                 cache(Key1)
             else solve(W.tail,V.tail,C)
         val sum2 = 
           if(currW<=C) {
              if(cache.containsKey(Key2))
                 cache(Key2)
              else solve(W.tail,V.tail,C-currW) + currV
            }
            else 0 
         cache((W.length,C)) = math.max(sum1,sum2)
         math.max(sum1,sum2)



       }
    }

    def traceSol(C: Int,W: List[Int]): List[Int] = {

         if(W.Length<1)
           nil
         else {
             val sum1 = cache((W.Length-1,C))
             val sum2 = cache((W.Length,C)) 
             if(sum1==sum2)
                traceSol(C,W.tail)
             else W.Length :: traceSol(C-W.head,W.tail)
         } 

    }

   val optval = solve(Weights,Values,Capacity)
   val solution = traceSol(Capacity,Weights)
   (optval,solution)

}
于 2013-11-14T05:47:41.483 回答
0

我想我发现了我的问题，忘记缓存一些案例，这是我的解决方案，最多 472 次迭代（迭代方法为 1650 次，即 N*W）

class KnapSackSolver() {

    var numberOfIterations = 0
    type Item = (Int, Int)
    type Items = List[Item]

    val cache = new HashMap[(Items, Int), Items]()

    def sackValue(s: Items) = if (s.isEmpty) 0 else s.map(_._2).sum

    def solve(wv: Items, capacity: Int) = {
      numberOfIterations = 0
      val solution = knapsack(wv, capacity)

      println(s"""|Solution: $solution
                  |Value: ${sackValue(solution)}
                  |Number of iterations: $numberOfIterations
      """.stripMargin)

      solution
    }

    private[this] def knapsack(wv: Items, capacity: Int): Items = {
      numberOfIterations += 1
      val cacheKey = (wv, capacity)
      if (cache.contains(cacheKey)) {
        cache(cacheKey)
      } else {
        val ret =
          if (capacity <= 0 || wv.isEmpty) {
            Nil
          } else if (wv.head._1 > capacity) {
            knapsack(wv.tail, capacity)
          } else {
            val sackNotTakingCurrent = knapsack(wv.tail, capacity)
            val sackTakingCurrent = wv.head :: knapsack(wv.tail, capacity - wv.head._1)

            val notTakingCurrentValue = sackValue(sackNotTakingCurrent)
            val takingCurrentValue = sackValue(sackTakingCurrent)
            if (notTakingCurrentValue >= takingCurrentValue) sackNotTakingCurrent
            else sackTakingCurrent

          }
        cache(cacheKey) = ret
        ret
      }

    }
  }
于 2013-11-13T22:11:35.883 回答