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