I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: The Knapsack Problem

11.29.2012
| 4996 views |
  • submit to reddit
Thursday is code puzzler day here at DZone. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

Do you have code puzzlers that you'd like to share with the DZone community?  If so, please submit here. 

The Knapsack Problem

Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit, and the total value is as large as possible

Catch up on all our previous puzzlers here.

Comments

Daniel Seidler replied on Thu, 2012/11/29 - 4:56am

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)]

Felix Kelm replied on Thu, 2012/11/29 - 5:22am

Calculating the optimal solution can be quite expensive - I think it's NP-complete. I had a similar problem when finding a subset of big files to fit on a DVD. I wrote a small program which calculated great solutions in some seconds.

Pseudocode is quite stupid but worked good for me ;-)

while(timeoutNotReached()) {
	bag = randomPackBagTillFull();
	if(bag.value > bestbag.value)
		bestbag = bag;		
}

Vijay Nathani replied on Thu, 2012/11/29 - 6:40am

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)]

Vijay Nathani replied on Thu, 2012/11/29 - 8:24am in response to: Vijay Nathani

My code has a bug. When

static def ITEMS = [ new Item(1,10), new Item(3,50), new Item (2,100) ]
 then for

println new Knapsack().getMaximumValue(3)

the answer printed is [Item(2,100].

The acutal answer should be [Item(1,10), Item(2,100)].

Please excuse.

Vijay Nathani replied on Thu, 2012/11/29 - 8:58am

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)]

Daniel Seidler replied on Thu, 2012/11/29 - 9:56am in response to: Vijay Nathani

Have you tried to run your code with more elements and capacity? I think because of subsequences() method you would run in OutOfMemoryException . With 30 elements you would need 1GB of heap space, with 31 2GB and so on.

 

Vijay Nathani replied on Thu, 2012/11/29 - 10:58am in response to: Daniel Seidler

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. 

Daniel Seidler replied on Thu, 2012/11/29 - 11:32am in response to: Vijay Nathani

Where this items unique? 

I'm not worried about memory. But in cases where acc has more than 30 unique items this algo. runs out of memory because of subsequences() will generate a Set > (2^30)-1 items. 


Vijay Nathani replied on Thu, 2012/11/29 - 1:31pm

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.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.