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

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

  /*
   * Die Menge M ist nicht so zu verstehen, dass die Gegenstände in einer Datenabstraktion vom Typ Set
   * stecken müssen. Es handelt sich um eine Menge von Gegenständen, die in irgendeiner Datenstruktur stecken.
   * Um möglichst nahe am Pseudocode zu bleiben, formulieren wir den Algorithmus zunächst in einer Variante,
   * die mit einer Kollektion  vom Typ Set arbeitet.
   * Das ist oft sinnvoll für den Prototyp einer Implementierung, mit dem dessen Korrektheit auf möglichst einfache
   * Art getestet wird. Oft erkennt man, dass ``Menge'' nicht wörtlich als Datentyp gemeint ist daran, dass
   * der Algorithmus die Auswahl eines beliebigen Elements erfordert:
   *
   * Wähle ein Objekt x in M aus
   *
   * Eine solche Auswahl ist keine ``natürliche'' Mengenoperation und wird nicht von jeder Set-Implementierung
   * unterstützt. Der Typ Set der Scala-API hat jedoch eine Methode head die irgendein Element der Menge liefert.
   * (Nicht notwendigerweise das erste, was immer man sich auch unter dem ersten Element einer Menge vorstellen mag.)
   */
  def KnapsackRek(M: Set[Item], T: Int): Set[Item] = {
    var S_opt = Set[Item]()
    var w_opt = 0

    def SearchTreeRek(M: Set[Item], T: Int, S: Set[Item], w: Int): Unit = {
      if (M.isEmpty) {
        if (w > w_opt) {
          S_opt = S
          w_opt = w
        }
      } else {
        val x: Item = M.head // ein beliebiges Element aus M
        val M_ : Set[Item] = M - x
        if (x.gewicht <= T) {
          val T_ = T - x.gewicht
          val S_ = S + x
          val w_ = w + x.wert
          SearchTreeRek(M_, T_, S_, w_)
        }
        SearchTreeRek(M_, T, S, w)
      }
    }

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

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


  val selection1 = KnapsackRek(items1.toSet, 10)
  val selection2 = KnapsackRek(items2.toSet, 200)
  val selection3 = KnapsackRek(items3.toSet, 20)

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


  /*
   * Die Verwendung des Typs Set verkompliziert die Sache nur unnötig. Statt in einer Datenstrukrur vom Typ Set,
   * wird die Menge der Gegenstände besser und einfacher in einer Liste gespeichert.
   * Eine Menge von Dingen kann ja durchaus in einer Liste gespeichert werden.
   * Das ergibt dann folgende Variante der Implementierung des Algorithmus:
   */

  def KnapsackRekList(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 // das erste Element von M
        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 items1a = List[Item](Item("A", 7, 42), Item("B", 3, 12), Item("C", 4, 40), Item("D", 5, 25))
  val items2a = List[Item](Item("Goldkorn", 1, 10), Item("Silberbarren", 200, 500))
  val items3a = List[Item](Item("Computer", 3, 300), Item("TV", 12, 200), Item("Uhr", 10, 150), Item("Vase", 7, 100))

  val selection1a = KnapsackRekList(items1a, 10)
  val selection2a = KnapsackRekList(items2a, 200)
  val selection3a = KnapsackRekList(items3a, 20)

  println("1: " + selection1a.mkString(", "))
  println("2: " + selection2a.mkString(", "))
  println("3: " + selection3a.mkString(", "))


}