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