How to solve Knapsack or Rucksack Algorithm using Dynamic programming

Knapsack or Rucksack Algorithm using Dynamic programming:

We're given n objects and a Knapsack or bag. Object i has weight w and the knapsack has a capacity m. If a fraction x_i such that 0≤ x_i ≤1 , of object i is placed into the knapsack then a profit of p_i x_i is earned. The objective is to obtain a filling of the knapsack that maximizes the total profit earned. Since the knapsack capacity is m, we require the total weight of all chosen objects to be at most m. Formally the problem can be stated as:

This problem can be solved using a brute force approach.

 Algorithm Bruteforce

Steps:

1.      Find (a set) all Possible configurations of the knapsack.
2.      Find a subset Ś of S such that Ś contains all possible combinations of  knapsack whose weight does not exceed the capacity C where 
3.  Find the configuration x_m of the knapsack with highest value belonging to Ś where

v(x) calculates the value of configuration x and w(x) calculates the weight of configuration x.

Example:

items = {1,2,3}

w = {10,5,20}

v = {3,6,1}

Tree:

S = { {},{2},{2,3},{1,2,3},{1,2},{1},{1,3} }

Weight = { 0, 5, 25, 35, 15, 10, 30 }

Capacity = 15

Ś = { {}, {2}, {1,2}, {1} }

Ś_w = { 0, 6, 9, 3 }

x_m = {1,2} where  

The Solution is {1,2}.

The complexity of this algorithm is O(2ⁿ).

After solving the problem using brute force it's clear that expanding the whole tree is unnecessary. Whenever we include an object in to the knapsack and the weight goes outside the capacity of the knapsack, we can stop the further expansion of that node. Based on this premise a selective expansion algorithm is developed and is shown below:

Algorithm Knapsack_Selective-Expansion:

Algorithm Knapsack(c,i)

{

            if i>n

                        return 0;

end

if c<w[i]

            return knapsack(c,i+1)

end

else

            max( knapsack(c,i+1), v[i]+knapsack(c-w[i],i+1) )

end

}

Using Memorization, we can write the new algorithm as

Algorithm Knapsack(c,i)

{

            if i>n

                        Table (c,i)=0;

                        return Table (c,i);

end

if c<w[i]

            if Table (c,i+1)=NULL

                        Table (c,i+1)=Knapsack(c,i+1)

            else

return Table (c,i+1)

end

if Table (c,i+1)=NULL

            Table (c,i+1)=Knapsack(c,i+1)

end

if Table (c-w[i], i+1)=NULL

            Table (c-w[i], i+1)=Knapsack(c-w[i], i+1)

end

else

            return max( Table(c,i+1), v[i]+Table(c-w[i],i+1) )

end

}

In this tree, we can see some overlapping sub problems. Now instead of solving the same problem multiple time, we can cache the result of a sub problem and can use this saved result whenever the sub problem need to be solved again. The below algorithm uses memorization to solve the knapsack problem.

●       Analysis:

We will be using transcript which is similar to a diary containing all the time steps. A time step is defined by a triplet. Each triplet of the transcript is of the given form:

        < Line Number, Maximum Capacity, Object Considered>

Hence, number of time steps = Line of Codes × Maximum Capacity × Number of Object

= O(1)×C×n

Hence the complexity of knapsack problem is O(Cn) when solved using Dynamic programming approach.