Knapsack problem/0-1: Difference between revisions
Added Kotlin
m (added links to ;Related tasks:) |
(Added Kotlin) |
||
Line 3,524:
Packed Weight: 396
Packed Value: 1030
</pre>
=={{header|Kotlin}}==
{{trans|Go}}
<lang scala>// version 1.1.1
data class Item(val name: String, val weight: Int, val value: Int)
val wants = listOf(
Item("map", 9, 150),
Item("compass", 13, 35),
Item("water", 153, 200),
Item("sandwich", 50, 160),
Item("glucose", 15, 60),
Item("tin", 68, 45),
Item("banana", 27, 60),
Item("apple", 39, 40),
Item("cheese", 23, 30),
Item("beer", 52, 10),
Item("suntan cream", 11, 70),
Item("camera", 32, 30),
Item("T-shirt", 24, 15),
Item("trousers", 48, 10),
Item("umbrella", 73, 40),
Item("waterproof trousers", 42, 70),
Item("waterproof overclothes", 43, 75),
Item("note-case", 22, 80),
Item("sunglasses", 7, 20),
Item("towel", 18, 12),
Item("socks", 4, 50),
Item("book", 30, 10)
)
const val MAX_WEIGHT = 400
fun m(i: Int, w: Int): Triple<MutableList<Item>, Int, Int> {
val chosen = mutableListOf<Item>()
if (i < 0 || w == 0) return Triple(chosen, 0, 0)
else if (wants[i].weight > w) return m(i - 1, w)
val (l0, w0, v0) = m(i - 1, w)
var (l1, w1, v1) = m(i - 1, w - wants[i].weight)
v1 += wants[i].value
if (v1 > v0) {
l1.add(wants[i])
return Triple(l1, w1 + wants[i].weight, v1)
}
return Triple(l0, w0, v0)
}
fun main(args: Array<String>) {
val (chosenItems, totalWeight, totalValue) = m(wants.size - 1, MAX_WEIGHT)
println("Knapsack Item Chosen Weight Value")
println("---------------------- ------ -----")
for (item in chosenItems.sortedByDescending { it.value} )
println("${item.name.padEnd(24)} ${"%3d".format(item.weight)} ${"%3d".format(item.value)}")
println("---------------------- ------ -----")
println("Total ${chosenItems.size} Items Chosen $totalWeight $totalValue")
}</lang>
{{out}}
<pre>
Knapsack Item Chosen Weight Value
---------------------- ------ -----
water 153 200
sandwich 50 160
map 9 150
note-case 22 80
waterproof overclothes 43 75
suntan cream 11 70
waterproof trousers 42 70
glucose 15 60
banana 27 60
socks 4 50
compass 13 35
sunglasses 7 20
---------------------- ------ -----
Total 12 Items Chosen 396 1030
</pre>
| |||