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(", ")) }