package kapitel_08

/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 8, Rucksack packen
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

object AuD_08_05_KnapsackDynProg_App extends App {

  case class Item(name: String, gewicht: Int, wert: Int)

  def KnapsackDP(M: List[Item], T: Int): List[Item] = {
    val n = M.length-1
    val Tab = Array.ofDim[Int](T+1, n+1)

    def TakeObject(i: Int, t: Int): Boolean = {
      if (M(i).gewicht <= t) {
        val rein = Tab(t - M(i).gewicht)(i - 1) + M(i).wert
        val raus = Tab(t)(i - 1)
        if (rein > raus)
          return true
      }
      false
    }

    // PHASE 1: Tabelle berechnen
    for (t <- 0 to T)
      Tab(t)(0) = 0
    for (i <- 1 to n) {
      Tab(0)(i) = 0
      for (t <- 1 to T)
        if (TakeObject(i, t)) {
          Tab(t)(i) = Tab(t-M(i).gewicht)(i-1) + M(i).wert
        } else {
          Tab(t)(i) = Tab(t)(i-1)
        }
    }

    // PHASE 2: Backtrace
    var S: List[Item] = Nil
    var t = T
    for (i <- n to 1 by -1) {
      if (TakeObject(i, t)) {
        S = M(i) :: S
        t = t - M(i).gewicht
      }
    }
    S
  }

  val items1 = List[Item](Item("Dummy", 0, 0), Item("A", 7, 42), Item("B", 3, 12), Item("C", 4, 40), Item("D", 5, 25))
  val items2 = List[Item](Item("Dummy", 0, 0), Item("Goldkorn", 1, 10), Item("Silberbarren", 200, 500))
  val items3 = List[Item](Item("Dummy", 0, 0), Item("Computer", 3, 300), Item("TV", 12, 200), Item("Uhr", 10, 150), Item("Vase", 7, 100))

  val selection1 = KnapsackDP(items1, 10)
  val selection2 = KnapsackDP(items2, 200)
  val selection3 = KnapsackDP(items3, 20)

  println("1: " + selection1.mkString(", "))
  println("2: " + selection2.mkString(", "))
  println("3: " + selection3.mkString(", "))

}