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 */ import scala.collection.mutable.ListBuffer import scala.util.Sorting object AuD_08_06_KnapsackDomi_App extends App { case class Item(name: String, gewicht: Int, wert: Int) def GetDominants(L: Array[List[Item]]): List[List[Item]] = { //sortiere L absteigend nach dem Wert Sorting.quickSort[List[Item]](L)( (a:List[Item], b:List[Item]) => b.map(_.wert).sum - a.map(_.wert).sum) //sortiere L stabil aufsteigend nach dem Gewicht Sorting.stableSort[List[Item]](L)( (a:List[Item], b:List[Item]) => a.map(_.gewicht).sum - b.map(_.gewicht).sum) var combi = L(0) val D = new ListBuffer[List[Item]] D += combi for (l <- L.drop(1)) { if (l.map(_.wert).sum > combi.map(_.wert).sum) { combi = l D += combi } } D.toList } def allSubLists[A](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 } val items = List[Item](Item("Computer", 3, 300), Item("TV", 12, 200), Item("Uhr", 10, 150), Item("Vase", 7, 100)) /* * Bei einer Tragkraft von 20 kg dominieren Computer, Vase und Uhr. */ GetDominants(allSubLists(items).toArray).foreach( l => { print(s"[${l.map(_.name).mkString(",")}] ") println(s" wert: ${l.map(_.wert).sum} gewicht: ${l.map(_.gewicht).sum}") }) def KnapsackDomi(M: List[Item], T: Int): List[Item] = { def GetDominants(L: Array[List[Item]]): List[List[Item]] = { Sorting.quickSort[List[Item]](L)( (a:List[Item], b:List[Item]) => b.map(_.wert).sum - a.map(_.wert).sum) Sorting.stableSort[List[Item]](L)( (a:List[Item], b:List[Item]) => a.map(_.gewicht).sum - b.map(_.gewicht).sum) var combi = L(0) val D = new ListBuffer[List[Item]] D += combi for (l <- L.drop(1)) { if (l.map(_.wert).sum > combi.map(_.wert).sum) { combi = l D += combi } } D.toList } var D: List[List[Item]] = List(Nil) for (mi <- M) { val L = new ListBuffer[List[Item]] for (combi <- D) { L += combi if (combi.map(_.gewicht).sum + mi.gewicht <= T) { L += mi :: combi } } D = GetDominants(L.toArray) } println(D) D.last } 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 = KnapsackDomi(items1, 10) val selection2 = KnapsackDomi(items2, 200) val selection3 = KnapsackDomi(items3, 20) println("1: " + selection1.mkString(", ")) println("2: " + selection2.mkString(", ")) println("3: " + selection3.mkString(", ")) }