54 lines
1.7 KiB
Kotlin
54 lines
1.7 KiB
Kotlin
// version 1.1.2
|
|
|
|
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")
|
|
}
|