/**
* 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_01_KnapsackGreedy {

    // Gegenstand, Attraktivität: Verhältnis Wert pro Gewicht
    struct Item : Comparable {
        let name : String
        let gewicht: Int
        let wert: Int
        var attraktion: Double {
            Double(wert) / Double(gewicht)
        }
        static func > (lhs: Item, rhs: Item) -> Bool {
            lhs.attraktion > rhs.attraktion
        }
        static func < (lhs: Item, rhs: Item) -> Bool {
            lhs.attraktion < rhs.attraktion
        }

    }

    static func KnapsackGreedy(M: [Item], T: Int) -> [Item] {

        // sortiere nach Attraktivität
        // Sortierung ist abwaerts nach Wert pro Gewicht
        let Msorted = M.sorted(by: >)

        var S: [Item] = []
        var g = 0
        for x in Msorted {
            if (g + x.gewicht <= T) {
                S = [x] + S
                g = g + x.gewicht
            }
        }
        return S
    }

    static func run () {
        let items: [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)]

        print("Auswahl =>  Gewicht : Wert")

        for i_0 in 0...1 {
            for i_1 in 0...1 {
                for i_2 in 0...1 {
                    for i_3 in 0...1 {
                        let selection: [Item] =
                                zip([i_0, i_1, i_2, i_3], items)
                                        .flatMap(
                                                { (x, item) in (x == 1) ? [item] : [] }
                                        )
                        let itemsNames = selection.map({ i in i.name }).joined(separator: ",")
                        let itemsWeight = selection.map({ i in i.gewicht }).reduce(0, +)
                        let itemsValue = selection.map({ i in i.wert }).reduce(0, +)
                        print("\(itemsNames) => \(itemsWeight) : \(itemsValue)")
                    }
                }
            }
        }

        print("")

        let selection = KnapsackGreedy(M: items, T: 10)

        print("Beste (gierige) Packung:")
        print(selection.map({ i in i.name }).joined(separator: ", "))

        print("==================================")

        /*
         * Silberbarren ist besser als Goldkorn:
         */

        let items2: [Item] = [Item(name: "Goldkorn", gewicht: 1, wert: 10), Item(name: "Silberbarren", gewicht: 200, wert: 500)]

        for i_0 in 0...1 {
            for i_1 in 0...1 {
                let selection: [Item] =
                        zip([i_0, i_1], items)
                                .flatMap(
                                        { (x, item) in (x == 1) ? [item] : [] }
                                )
                let itemsNames = selection.map({ i in i.name }).joined(separator: ",")
                let itemsWeight = selection.map({ i in i.gewicht }).reduce(0, +)
                let itemsValue = selection.map({ i in i.wert }).reduce(0, +)
                print("\(itemsNames) => \(itemsWeight) : \(itemsValue)")
            }
        }

        print("")

        /*
         * Bei Goldkorn und dem Silberbarren versagt die Gier:
         */
        let selection2: [Item] = KnapsackGreedy(M: items2, T: 200)
        print("Beste (gierige) Packung:")
        print(selection2.map({ i in i.name }).joined(separator: ", "))
    }

}