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_04_KnapsackBnB_App extends App {

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

  def KnapsackBnB(M: List[Item], T: Int): List[Item] = {
    var S_opt = List[Item]()
    var w_opt = 0

    def SearchTreeRek(M: List[Item], T: Int, S: List[Item], w: Int): Unit = {
      if (M.isEmpty) {
        if (w > w_opt) {
          S_opt = S
          w_opt = w
        }
      } else {
        val x: Item = M.head
        // BnB:
        val w_rest = M.foldLeft(0)( (acc: Int, item: Item) => acc + item.wert )
        if (w + w_rest <= w_opt) return

        val M_ : List[Item] = M.tail
        if (x.gewicht <= T) {
          val T_ = T - x.gewicht
          val S_ = x :: S
          val w_ = w + x.wert
          SearchTreeRek(M_, T_, S_, w_)
        }
        SearchTreeRek(M_, T, S, w)
      }
    }

    SearchTreeRek(M, T, List[Item](), 0)
    S_opt
  }

  val items = List[Item](Item("Computer", 3, 300), Item("TV", 12, 200), Item("Uhr", 10, 150), Item("Vase", 7, 100))

  val selection = KnapsackBnB(items, 20)

  println(selection.mkString(", "))

}