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

  /*
   * Im Pseudocode wird eine Menge und ihre telmengen verwendet. Das ist
   * wieder nicht so zu verstehen, dass im Code mit dem Typ Set gearbeitet werden soll.
   * es handelt sich um eine Menge von Elementen, die in irgendeiner Datstruktur stecken.
   * Wir nehmen eine Liste als Datenstruktur.
   *
   * Die Menge aller Teilmengen einer Menge $M$ mit $|M|$ Elementen können wir finden indem wir alle
   * Kombinationen von 0 und 1 der Länge |M| als Auswahlfunktion auf M anwenden.
   * Die Kombinationen können bei bekannter Länge mit geschachtelten for-Schleifen gefunden werden.
   * Bei unbekannte Länge können die Schleifen rekursiv erzeugt werden:
   */
  case class AllSubListsViaBitSequence[A](lst: List[A]) extends Iterable[List[A]] {
    override def iterator: Iterator[List[A]] =
      allSubLists(lst).iterator

    private def allSubLists(lst: List[A]): List[List[A]] =
      for (selection <- bitSeqOfLength(lst.length))
        yield lst.zipWithIndex.flatMap {
          case (item, index) =>
            if (selection(index) == 0) List() else List(item)
        }

    private def bitSeqOfLength(n: Int): List[List[Int]] =
      if (n == 0)
        List(Nil)
      else
        for (s <- bitSeqOfLength(n-1);
             b <- 0 to 1
        ) yield b :: s
  }


  /*
   * Es ist nicht notwendig die Folgen von  Nullen und Einsen zu bilden.
   * Man kann auch gleich die Liste der Möglichkeiten auch erzeugen:
   */
  case class AllSubLists[A](lst: List[A]) extends Iterable[List[A]] {
    override def iterator: Iterator[List[A]] =
      allSubLists(lst).iterator

    private def allSubLists(lst: List[A]): List[List[A]] = lst match {
      case Nil =>
        List(Nil)
      case head :: tail =>
        for (s <- allSubLists(tail);
             b <- List(List(head), Nil)
        ) yield s ++ b
    }
  }

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

  def KnapsackBruteForce(M: List[Item], T: Int): List[Item] = {
    var S_opt = List[Item]()
    var w_opt = 0
    for (s <- AllSubLists(M)) {
      val w = s.map( _.wert ).sum
      val g = s.map( _.gewicht ).sum
      if ((g <= T) && (w > w_opt)) {
        S_opt = s
        w_opt = w
      }
    }
    S_opt
  }

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

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

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

}