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_07_KnapsackApprox_App extends App { case class Item(name: String, gewicht: Int, wert: Int) class ItemReduced(item: Item, r: Double) extends Item(item.name, item.gewicht, (item.wert/r).toInt) { val urwert: Int = item.wert } def KnapsackDomi[I <: Item](M: List[I], T: Int): List[I] = { def GetDominants(L: Array[List[I]]): List[List[I]] = { Sorting.quickSort[List[I]](L)( (a:List[Item], b:List[I]) => b.map(_.wert).sum - a.map(_.wert).sum) Sorting.stableSort[List[I]](L)( (a:List[Item], b:List[I]) => a.map(_.gewicht).sum - b.map(_.gewicht).sum) var combi = L(0) val D = new ListBuffer[List[I]] 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[I]] = List(Nil) for (mi <- M) { val L = new ListBuffer[List[I]] for (combi <- D) { L += combi if (combi.map(_.gewicht).sum + mi.gewicht <= T) { L += mi :: combi } } D = GetDominants(L.toArray) } D.last } def KnapsackApprox(M: List[Item], T: Int, epsilon: Double): List[Item] = { val w_max: Int = M.maxBy(_.wert).wert val r: Double = (epsilon * w_max) / M.length val Mreduced = M.map( item => new ItemReduced(item, r) ) val S: List[ItemReduced] = KnapsackDomi(Mreduced, T) S.map( iR => Item(iR.name, iR.gewicht, iR.urwert)) } 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 = KnapsackApprox(items1, 10, 0.5) val selection2 = KnapsackApprox(items2, 200, 0.5) val selection3 = KnapsackApprox(items3, 20, 0.5) println("1: " + selection1.mkString(", ")) println("2: " + selection2.mkString(", ")) println("3: " + selection3.mkString(", ")) }