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

  // Attraktivität: Verhältnis Wert pro Gewicht
  case class Item(name: String, gewicht: Int, wert: Int)

  /*
   * Die Menge M im Pseudocode ist nicht als Datenstruktur zu verstehen, sondern als Menge von Werten,
   * die in irgendeiner Datenstruktur stecken.
   * Da der Algorithmus mit einer Sortiereung der ``Menge'' beginnt, nehmen wir eine Datenstruktur, die am
   * Platz sortierbar ist: ein Array.
   */
  def KnapsackGreedy(M: Array[Item], T: Int): List[Item] = {
    import scala.util.Sorting

    // sortiere nach Attraktivität
    // Sortierung ist abwaerts nach Wert pro Gewicht
    Sorting.quickSort(M)( // Sortier-Ordnung
      (x: Item, y: Item) =>
        (((y.wert+0.0) / y.gewicht) - ((x.wert+0.0) / x.gewicht)).toInt)

    var S = List[Item]()
    var g = 0
    for (x <- M) {
      if (g + x.gewicht <= T) {
        S = x :: S
        g = g + x.gewicht
      }
    }
    S
  }

  val items = Array[Item](Item("A", 7, 42), Item("B", 3, 12), Item("C", 4, 40), Item("D", 5, 25))

  /*
   * Um zu sehen, ob das korrekt ist, lassen wir uns Gewicht und aller Kombinationen ausgeben.
   * Eine Kombination ist eine Teilmenge aller Gegenstände.
   * Bei vier Gegenständen ist das eine überschaubare Menge an Möglichkeiten, die wir einfach mit
   * vier Schleifen erzeugen können:
   */

  println("   Auswahl   Gewicht Wert")
  for (i_0 <- 0 to 1 )
    for (i_1 <- 0 to 1 )
      for (i_2 <- 0 to 1 )
        for (i_3 <- 0 to 1 ) {
          val selection =
            List(i_0, i_1, i_2, i_3).zip(items)
              .flatMap {
                case (x, item) => if (x == 1) List(item) else Nil
              }
          print(f"${selection.map(_.name).mkString(",")}%10s    ")
          println(f"${selection.map(_.gewicht).sum}%4d ${selection.map(_.wert).sum}%4d")
        }

  println("------------------------")

  val selection = KnapsackGreedy(items, 10)
  println(selection.mkString(", "))
  println()
  println("==================================")

  /*
   * Silberbarren ist besser als Goldkorn:
   */

  val items2 = Array[Item](Item("Goldkorn", 1, 10), Item("Silberbarren", 200, 500))

  println("   Auswahl             Gewicht Wert")
  for (i_0 <- 0 to 1 )
    for (i_1 <- 0 to 1 ) {
          val selection =
            List(i_0, i_1).zip(items2)
              .flatMap {
                case (x, item) => if (x == 1) List(item) else Nil
              }
          print(f"${selection.map(_.name).mkString(",")}%20s    ")
          println(f"${selection.map(_.gewicht).sum}%4d ${selection.map(_.wert).sum}%4d")
        }
  println()

  println("------------------------")

  /*
   * Bei Goldkorn und dem Silberbarren versagt die Gier:
   */
  val selection2 = KnapsackGreedy(items2, 200)
  println(selection2.mkString(", "))

}