Knapsack problem/Bounded: Difference between revisions
Added Kotlin
(Added Kotlin) |
|||
Line 1,772:
Packed Weight: 396
Packed Value: 1010
</pre>
=={{header|Kotlin}}==
{{trans|C}}
<lang scala>// version 1.1.1
data class Item(val name: String, val weight: Int, val value: Int, val count: Int)
val items = listOf(
Item("map", 9, 150, 1),
Item("compass", 13, 35, 1),
Item("water", 153, 200, 2),
Item("sandwich", 50, 60, 2),
Item("glucose", 15, 60, 2),
Item("tin", 68, 45, 3),
Item("banana", 27, 60, 3),
Item("apple", 39, 40, 3),
Item("cheese", 23, 30, 1),
Item("beer", 52, 10, 3),
Item("suntan cream", 11, 70, 1),
Item("camera", 32, 30, 1),
Item("T-shirt", 24, 15, 2),
Item("trousers", 48, 10, 2),
Item("umbrella", 73, 40, 1),
Item("waterproof trousers", 42, 70, 1),
Item("waterproof overclothes", 43, 75, 1),
Item("note-case", 22, 80, 1),
Item("sunglasses", 7, 20, 1),
Item("towel", 18, 12, 2),
Item("socks", 4, 50, 1),
Item("book", 30, 10, 2)
)
val n = items.size
const val MAX_WEIGHT = 400
fun knapsack(w: Int): IntArray {
val m = Array(n + 1) { IntArray(w + 1) }
for (i in 1..n) {
for (j in 0..w) {
m[i][j] = m[i - 1][j]
for (k in 1..items[i - 1].count) {
if (k * items[i - 1].weight > j) break
val v = m[i - 1][j - k * items[i - 1].weight] + k * items[i - 1].value
if (v > m[i][j]) m[i][j] = v
}
}
}
val s = IntArray(n)
var j = w
for (i in n downTo 1) {
val v = m[i][j]
var k = 0
while (v != m[i - 1][j] + k * items[i - 1].value) {
s[i - 1]++
j -= items[i - 1].weight
k++
}
}
return s
}
fun main(args: Array<String>) {
val s = knapsack(MAX_WEIGHT)
println("Item Chosen Weight Value Number")
println("--------------------- ------ ----- ------")
var itemCount = 0
var sumWeight = 0
var sumValue = 0
var sumNumber = 0
for (i in 0 until n) {
if (s[i] == 0) continue
itemCount++
val name = items[i].name
val number = s[i]
val weight = items[i].weight * number
val value = items[i].value * number
sumNumber += number
sumWeight += weight
sumValue += value
println("${name.padEnd(22)} ${"%3d".format(weight)} ${"%4d".format(value)} ${"%2d".format(number)}")
}
println("--------------------- ------ ----- ------")
println("Items chosen $itemCount ${"%3d".format(sumWeight)} ${"%4d".format(sumValue)} ${"%2d".format(sumNumber)}")
}</lang>
{{out}}
<pre>
Item Chosen Weight Value Number
--------------------- ------ ----- ------
map 9 150 1
compass 13 35 1
water 153 200 1
glucose 30 120 2
banana 81 180 3
cheese 23 30 1
suntan cream 11 70 1
waterproof overclothes 43 75 1
note-case 22 80 1
sunglasses 7 20 1
socks 4 50 1
--------------------- ------ ----- ------
Items chosen 11 396 1010 14
</pre>
| |||