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

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

    static func KnapsackBnB(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.count == 0) {
                if (w > w_opt) {
                    S_opt = S
                    w_opt = w
                }
            } else {
                let x: Item = M[0]
                // BnB:
                let w_rest = M.reduce(0, { (acc: Int, item: Item) in acc + item.wert } )
                if (w + w_rest <= w_opt) {
                    return
                }
                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 items: [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 selection = KnapsackBnB(M: items, T: 20)

        print(selection.map({ i in i.description }).joined(separator: ", "))
    }

}