83 lines
2.0 KiB
Swift
83 lines
2.0 KiB
Swift
public struct KnapsackItem: Hashable {
|
|
public var name: String
|
|
public var weight: Int
|
|
public var value: Int
|
|
|
|
public init(name: String, weight: Int, value: Int) {
|
|
self.name = name
|
|
self.weight = weight
|
|
self.value = value
|
|
}
|
|
}
|
|
|
|
public func knapsack(items: [KnapsackItem], limit: Int) -> [KnapsackItem] {
|
|
var table = Array(repeating: Array(repeating: 0, count: limit + 1), count: items.count + 1)
|
|
|
|
for j in 1...items.count {
|
|
let item = items[j-1]
|
|
|
|
for w in 1...limit {
|
|
if item.weight > w {
|
|
table[j][w] = table[j-1][w]
|
|
} else {
|
|
table[j][w] = max(table[j-1][w], table[j-1][w-item.weight] + item.value)
|
|
}
|
|
}
|
|
}
|
|
|
|
var result = [KnapsackItem]()
|
|
var w = limit
|
|
|
|
for j in stride(from: items.count, to: 0, by: -1) where table[j][w] != table[j-1][w] {
|
|
let item = items[j-1]
|
|
|
|
result.append(item)
|
|
|
|
w -= item.weight
|
|
}
|
|
|
|
return result
|
|
}
|
|
|
|
typealias GroupedItem = (name: String, weight: Int, val: Int, n: Int)
|
|
|
|
let groupedItems: [GroupedItem] = [
|
|
("map", 9, 150, 1),
|
|
("compass", 13, 35, 1),
|
|
("water", 153, 200, 3),
|
|
("sandwich", 50, 60, 2),
|
|
("glucose", 15, 60, 2),
|
|
("tin", 68, 45, 3),
|
|
("banana", 27, 60, 3),
|
|
("apple", 39, 40, 3),
|
|
("cheese", 23, 30, 1),
|
|
("beer", 52, 10, 3),
|
|
("suntan cream", 11, 70, 1),
|
|
("camera", 32, 30, 1),
|
|
("t-shirt", 24, 15, 2),
|
|
("trousers", 48, 10, 2),
|
|
("umbrella", 73, 40, 1),
|
|
("waterproof trousers", 42, 70, 1),
|
|
("waterproof overclothes", 43, 75, 1),
|
|
("note-case", 22, 80, 1),
|
|
("sunglasses", 7, 20, 1),
|
|
("towel", 18, 12, 2),
|
|
("socks", 4, 50, 1),
|
|
("book", 30, 10, 2)
|
|
]
|
|
|
|
let items = groupedItems.flatMap({item in
|
|
(0..<item.n).map({_ in KnapsackItem(name: item.name, weight: item.weight, value: item.val) })
|
|
})
|
|
|
|
let bagged = knapsack(items: items, limit: 400)
|
|
let (totalVal, totalWeight) = bagged.reduce((0, 0), {cur, item in (cur.0 + item.value, cur.1 + item.weight) })
|
|
|
|
print("Bagged the following \(bagged.count) items:")
|
|
|
|
for item in bagged {
|
|
print("\t\(item.name)")
|
|
}
|
|
|
|
print("For a total value of \(totalVal) and weight of \(totalWeight)")
|