knapsack.swift

struct Item {

    let description: String
    let weight: Int
    let value: Int
    let quantity: Int

    init(description: String, weight: Int, value: Int, quantity: Int) {
        self.description = description
        self.weight = weight
        self.value = value
        self.quantity = quantity
    }
}

//create some items
var items: [Item] = [
    Item(description: "Apple",  weight: 2, value: 5, quantity: 1),
    Item(description: "Banana", weight: 8, value: 3, quantity: 1),
    Item(description: "Beer",   weight: 4, value: 2, quantity: 1),
    Item(description: "Book",   weight: 2, value: 7, quantity: 1),
    Item(description: "Camera", weight: 5, value: 4, quantity: 1)
]

//max weight allowed
let capacity: Int = 20

class ItemCollection {

    var contents: [String: Int] = [String: Int]()
    var totalValue: Int = 0
    var totalWeight: Int = 0

    func addItem(item: Item, quantity: Int) -> ItemCollection {
        if let value = contents[item.description] {
            contents[item.description] = value + quantity
        }
        else {
            contents[item.description] = quantity
        }

        totalValue += quantity * item.value
        totalWeight += quantity * item.weight

        return self
    }

    func copy() -> ItemCollection {
        let ic = ItemCollection()
        ic.contents = contents
        ic.totalValue = totalValue;
        ic.totalWeight = totalWeight;
        return ic
    }
}


var ic = [ItemCollection]()

print(capacity)
for i in 0..<(capacity+1) {
    ic.append(ItemCollection())
}

print(items)
for i in 0..<items.count {
    print(i)
    for j in (0..<capacity).reverse() {
        print(j)
        if j >= items[i].weight {
            let quantity: Int = min(items[i].quantity, j / items[i].weight)
            for k in 1..<(quantity+1) {
                let lighterCollection: ItemCollection = ic[j - k * items[i].weight]
                let testValue: Int = lighterCollection.totalValue + k * items[i].value
                if testValue > ic[j].totalValue {
                    ic[j] = lighterCollection.copy().addItem(items[i], quantity: k)
                }
            }
        }
    }
}

// Remove empty last
ic.removeLast()

print("\(ic.last?.contents)")