Knapsack Problem - Theory, Algorithm, Example, Math for Computer Science Students

Knapsack Problem - Theory, Algorithm, Example, Math for Computer Science Students

Knapsack problem demonstration - From (Sartaj Sahni Book):

There are n objects and a knapsack or bag. Object i has a weight wi and the knapsack has the capacity m. If a fraction xi, 0<=xi<=1, of object i is placed into the knapsack, then a profit of pixi is earned. The objective is to obtain a fiiling 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. So, we can say the problem as below -

i = object
w = weight
m = capacity
maximize profit = ∑pixi
total weight = ∑wixi

The profits and weights will be the positive numbers






Algorithm Knapsack Problem (Sartaj Sahni Book):

Algorithm Greedy Knapsack(m, n)
// P[1:n] and W[1:n] contain the profit and the weight respectively
// of the n objectives such that P[i]/W[i] >= P[i+1]/W[i+1]
// m is the knapsack size and x[1:n] is the solution vector
{
    for i = 1 to n do x[i] = 0.0
    U = m;
    for i = 1 to n do
    {
        if (W[i] > U) then break
        x[i] = 1.0; U = U - W[i]
    }
  if (i <= n) then x[i] = U/W[i]
}

Math Example Knapsack Problem (Sartaj Sahni Book):

Example: Consider the following instances of Knapsack problem: n=3, m=20, (P1, P2, P3) = (25, 24, 15) and (W1, W2, W3) = (18, 15, 10). What are the feasible and optimal solution for this Knapsack problem?

Solution: 

Feasible solutions are:

x1	x2	x3	wixi	pixi
1/2	1/3	1/4	9+5+2.5 = 16.5	12+8+3.75 = 23.75
1	2/15	0	18+2+0 = 20	25+3.2+0 = 28.2
0	2/3	1	0+10+10 = 20	0+16+15 = 31.0
0	1	1/2	0+15+5 = 20	0+24+7.5 = 31.5

So, we can see there there are four feasible solutions but there is one solution where the profit maximize. The maximum profit is 31.5. So, this is the optimal solution for Knapsack Problem.

Optimal solution finding technique short-cut:

We may consider there is 3 Jobs because there is 3 weights. Jobs are J1, J2, J3.
J1 = P1/W1 = 25/18 = 1.38
J2 = P2/W2 = 24/15 = 1.6
J3 = P3/W3 = 15/10 = 1.5

So, here Job 1.6>1.5>1.38 and jobs priority is = J2>J3>J1

x1	x2	x3	wixi	pixi
0	1	1/2	0+15+5 = 20	0+24+7.5 = 31.5

Concept Theory from Wikipedia:

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.

Learn More about Knapsack Problem


Tags:
Knapsack Problem - Theory, Algorithm, Example, Math for Computer Science Students, Knapsack Problem example, Knapsack Problem Algorithm, Knapsack Problem Code, Knapsack Problem Math,