Thursday Code Puzzler: The Knapsack Problem

Kotlin

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)));
}

Output

[Item(weight=2, value=100), Item(weight=2, value=90), Item(weight=1, value=10), Item(weight=5, value=700)]

Groovy code

@groovy.transform.Immutable class Item { int weight, value; }
class Knapsack {
	static def ITEMS = [ new Item(1,10), new Item(3,20), new Item (2,30) ]
	private def currentSolution, currentValue
	private def void addMaximumNumberOfItemsPossible(item, maxWeight) {
		while (true) {
			def newSolution = (currentSolution + item).subsequences().max { i -> (i.sum{it.weight} <= maxWeight)? i.sum{it.value} : 0 }
			if (newSolution.sum { it.value } <= currentValue) return
			(currentSolution, currentValue) = [newSolution, newSolution.sum { it.value } ]
		}
	}
	def getMaximumValue(maxWeight) {
		(currentSolution, currentValue) = [ [], 0 ]
		ITEMS.each { addMaximumNumberOfItemsPossible(it, maxWeight) }	
		currentSolution
	}
}
println new Knapsack().getMaximumValue(3) 

The output is: [Item(1, 10), Item(2, 30)]

My new solution in Groovy is

@groovy.transform.Immutable class Item { int weight, value; }
def ITEMS = [ new Item(1,10), new Item(3,50), new Item (2,50) ]
def knapsack =  { maxWeight ->
	ITEMS.inject([]) { acc,item -> (maxWeight / item.weight).times {acc.push(item) }; acc } .subsequences().max { i -> (i.sum{it.weight} <= maxWeight)? i.sum{it.value} : 0 }
}
println knapsack(3) 

This code prints the right solution: [Item(1, 10), Item(2, 50)]

For 12 items, it takes 0.6 GB total memory (code + stack + heap + data) in taskmgr.exe on 64 bit Windows 7 ultimate. My environment is

Groovy Version: 2.0.5 JVM: 1.7.0_09 Vendor: Oracle Corporation OS: Windows 7

If you are worried about memory, then I can write a function that combines the subsequence and max functionality. So intermediate values will not be stored. 

To save memory, I have combined subsequence and max functions in the following groovy code.

@groovy.transform.Immutable class Item { int weight, value; }
def ITEMS = [ new Item(1,10), new Item(3,50), new Item(2,50)]
def knapsack =  { maxWeight ->
	subsequenceMax(ITEMS.inject([]) { a,v -> a + [v] * (maxWeight / v.weight)  }, { i -> (i.sum{it.weight} <= maxWeight)? i.sum{it.value} : 0 } )
}
def subsequenceMax (values, codeBlock) {
		def (currentMax, tempMax, maxSeq) = [0, 0, []]
		def indexes = ([0] * values.size()).toArray()
		for (int i=0; indexes[0] < values.size();) {
			def current = []
			(0..i).each { current.push(values[indexes[it]]) }
			if (( tempMax =codeBlock(current)) > currentMax) 
				(currentMax, maxSeq) = [tempMax, current ]
			if (++i >= values.size() || indexes[i-1] +1 >= values.size()) 
				for (--i; i>=0 && ++indexes[i] >= values.size(); )
					--i
			else 
				indexes[i] = indexes[i-1]+1
		}
		maxSeq 
}
println knapsack(3)

Now, the memory consumption will not increase exponentially. Thanks Daniel.