/**
 * 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 Foundation

struct AuD_08_03_KnapsackRek {

    struct Item : CustomStringConvertible {
        let name : String
        let gewicht: Int
        let wert: Int
        var description: String {
            "(\(name), \(gewicht), \(wert))"
        }
    }

    /*
     * Die Menge M ist nicht so zu verstehen, dass die Gegenstände in einer Datenabstraktion vom Typ Set
     * stecken müssen. Es handelt sich um eine Menge von Gegenständen, die in irgendeiner Datenstruktur stecken.
     * Um möglichst nahe am Pseudocode zu bleiben, formulieren wir den Algorithmus zunächst in einer Variante,
     * die mit einer Kollektion  vom Typ Set arbeitet.
     * Das ist oft sinnvoll für den Prototyp einer Implementierung, mit dem dessen Korrektheit auf möglichst einfache
     * Art getestet wird. Oft erkennt man, dass ``Menge'' nicht wörtlich als Datentyp gemeint ist daran, dass
     * der Algorithmus die Auswahl eines beliebigen Elements erfordert:
     *
     * Wähle ein Objekt x in M aus
     *
     * Eine solche Auswahl ist keine ``natürliche'' Mengenoperation und wird nicht von jeder Set-Implementierung
     * unterstützt. Statt in einer Datenstrukrur vom Typ Set,
     * wird die Menge der Gegenstände besser und einfacher in einer Liste gespeichert.
     * Eine Menge von Dingen kann ja durchaus in einer Liste gespeichert werden.
     * Das ergibt dann folgende Variante der Implementierung des Algorithmus:
     */

    static func KnapsackRekList(M: [Item], T: Int) -> [Item] {
        var S_opt : [Item] = []
        var w_opt = 0

        func SearchTreeRek(M: [Item], T: Int, S: [Item], w: Int) {
            if (M.isEmpty) {
                if (w > w_opt) {
                    S_opt = S
                    w_opt = w
                }
            } else {
                let x: Item = M[0] // das erste Element von M
                let M_ : [Item] = Array(M.dropFirst())
                if (x.gewicht <= T) {
                    let T_ = T - x.gewicht
                    let S_ = [x] + S
                    let w_ = w + x.wert
                    SearchTreeRek(M: M_, T: T_, S: S_, w: w_)
                }
                SearchTreeRek(M: M_, T: T, S: S, w: w)
            }
        }

        SearchTreeRek(M: M, T: T, S: [], w: 0)
        return S_opt
    }

    static func run() {
        let items1: [Item] = [Item(name: "A", gewicht: 7, wert: 42), Item(name: "B", gewicht: 3, wert: 12), Item(name: "C", gewicht: 4, wert: 40), Item(name: "D", gewicht: 5, wert: 25)]
        let items2: [Item] = [Item( name: "Goldkorn", gewicht: 1, wert: 10), Item(name: "Silberbarren", gewicht: 200, wert: 500)]
        let items3: [Item] = [Item(name: "Computer", gewicht: 3, wert: 300), Item(name: "TV", gewicht: 12, wert: 200), Item(name: "Uhr", gewicht: 10, wert: 150), Item(name: "Vase", gewicht: 7, wert: 100)]

        let selection1 = KnapsackRekList(M: items1, T: 10)
        let selection2 = KnapsackRekList(M: items2, T: 200)
        let selection3 = KnapsackRekList(M: items3, T: 20)

        print(selection1.map( { i in i.description } ).joined(separator: ", ") )
        print(selection2.map( { i in i.description } ).joined(separator: ", ") )
        print(selection3.map( { i in i.description } ).joined(separator: ", ") )
    }

}