Knapsack problem/Bounded: Difference between revisions

</pre>

=={{header|Swift}}==

{{trans|Python}}

<lang 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)")</lang>

{{out}}

<pre>Bagged the following 14 items:

socks

sunglasses

note-case

waterproof overclothes

suntan cream

cheese

banana

banana

banana

glucose

glucose

water

compass

map

For a total value of 1010 and weight of 396