#Day 10

As Wikipedia says

The

knapsack problemorrucksack problemis 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

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.