0-1 Knapsack Problem

#Day 10

As Wikipedia says

The knapsack problem or rucksack problem is a problem in combinatorial optimization: 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. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.

We will solve this problem using the bottom-up approach of dynamic programming. Let’s start with an example –

We have weights as 3,1,4,5 and their respective values are 4,1,5,7 and the maximum weight we can carry in the knapsack is 7. And we have only one supply of each item.

We need to create a table of size (n*(m+1)) where n is the number of items and m is the maximum weight.

For filling up the whole table to get the desired result we apply the following rules for each field in the table.

If row==0:

if column >=weight[row]

table[row][column]=value[row]

else

table[row][column]=0

else

if column >=weight[row]

table[row][column]=max(value[row]+table[row-1][column-weight[row]],table[row-1][column])

else

table[row][column]=table[row-1][column]

 

def knapsack(weights,values,maximum_weight):
    heightOfTable = len(values)
    weightTable = [[0 for x in xrange(maximum_weight+1)] for y in xrange(heightOfTable)]
    for column in xrange(weights[0],maximum_weight+1):
        weightTable[0][column]=values[0]
    for row in xrange(1,heightOfTable):
        for column in xrange(maximum_weight+1):
            if column>=weights[row]:
                weightTable[row][column]=max(values[row]+weightTable[row-1][column-weights[row]],weightTable[row-1][column])
            else:
                weightTable[row][column]=weightTable[row-1][column]

    return weightTable

By applying above rules we get following table steps by steps

 

knap1
Image: 1

 

knap2
Image: 2

 

knap3
Image: 3

 

knap4
Image: 4

 

knap5
Image: 5

As we get the final table, the maximum value we can get is table[lastRow][lastColumn].

 

The same rule we used to create the rule can be applied to get the exact items we chose.

Time Complexity

The time complexity of this algorithm is O(nm). n the number of items and m is the maximum weight.

 

Source Code

 

Source code for implementation of this algorithm can be found here.

Extension and variation

 

This problem can be extended if we have the infinite supply of each item. But if we are allowed to choose the item partially then this problem can be solved using greedy algorithm. Just need to sort all the items with their value/weight score and choose the items in the order.

 

 

 

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s