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回の繰り返し）が、それを改善する方法がわかりません。

言い換えれば、これは最適な解決策ですか? 私には非常に指数関数的に感じますが、疑似多項式が実際に何を意味するのかを理解していると言ったら嘘をつきます.

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 に答える