Knapsack Solver

Knapsack.kt

import java.util.ArrayList

/**
 * @author Daniel Seidler
 * @since 2012/11/29
 */


data class Item(val weight: Int, val value: Int)

class Knapsack(val capacity: Int) {
    fun pack(vararg items: Item): List<Item> {
        val result = ArrayList<Item>()
        val matrix = calc(items.toList())
        var i = items.size
        var j = capacity
        while (i != 0 && j != 0)
            when{
                matrix[i][j] == matrix[i - 1][j] -> i--
                else -> {
                    j -= items.get(--i).weight
                    result.add(items.get(i))
                }
            }
        return result
    }

    fun calc(val items: List<Item>): Array<Array<Int>> {
        val matrix = Array<Array<Int>>(items.size + 1, { Array<Int>(capacity + 1, { 0 }) })
        for((i, item) in items.withIndices())
            for(capacity in 1..capacity)
                when{
                    item.weight > capacity -> matrix[i + 1][capacity] = matrix[i][capacity]
                    else                   -> matrix[i + 1][capacity] = Math.max(matrix[i][capacity], item.value + matrix[i][capacity - item.weight])
                }
        return matrix;
    }
}

fun main(args: Array<String>) {
    println(Knapsack(10).pack(Item(5, 700), Item(1, 10), Item(2, 70), Item(2, 90), Item(2, 100)));
}