Module 2(b)

Knapsack Problem

Here knapsack is like a container or a bag. Suppose we have given some items which have
some weights or profits. We have to put some items in the knapsack in such a way total
value produces a maximum profit.
For example, the weight of the container is 20 kg. We have to select the items in such a way
that the sum of the weight of items should be either smaller than or equal to the weight of
the container, and the profit should be maximum.
There are two types of knapsack problems:
o 0/1 knapsack problem
o Fractional knapsack problem

0/1 Knapsack Problem

The 0/1 knapsack problem means that the items are either completely or no items are filled
in a knapsack. For example, we have two items having weights 2kg and 3kg, respectively. If
we pick the 2kg item then we cannot pick 1kg item from the 2kg item (item is not divisible);
we have to pick the 2kg item completely. This is a 0/1 knapsack problem in which either we
pick the item completely or we will pick that item. The 0/1 knapsack problem is solved by
the dynamic programming.
Given N items where each item has some weight and profit associated with it and also given
a bag with capacity W, [i.e., the bag can hold at most W weight in it]. The task is to put the
items into the bag such that the sum of profits associated with them is the maximum
possible.
Note: The constraint here is we can either put an item completely into the bag or cannot put
it at all [It is not possible to put a part of an item into the bag].
Below is an explanation of the problem, its formulation, and how to solve it.
Problem Statement
You are given:
1. n items, each with:
o Weight wi
o Value vi
2. A knapsack that can carry a maximum weight W.
The goal is to determine the maximum value that can be obtained by selecting a subset of
items, such that the total weight does not exceed W. You can either:
 Include an item (1), or
 Exclude an item (0).
Hence the name 0/1 Knapsack.
Example: Input: N = 3, W = 4, profit[] = {1, 2, 3}, weight[] = {4, 5, 1}
Output:3
Explanation: There are two items which have weight less than or equal to 4. If
we select the item with weight 4, the possible profit is 1. And if we select the item
with weight 1, the possible profit is 3. So the maximum possible profit is 3. Note
that we cannot put both the items with weight 4 and 1 together as the capacity of
the bag is 4.
Example of 0/1 knapsack problem.
Consider the problem having weights and profits are:

Weights: {3, 4, 6, 5}

Profits: {2, 3, 1, 4}

The weight of the knapsack is 8 kg

The number of items is 4

The above problem can be solved by using the following method:

xi = {1, 0, 0, 1}

= {0, 0, 0, 1}

= {0, 1, 0, 1}

The above are the possible combinations. 1 denotes that the item is completely picked and 0
means that no item is picked. Since there are 4 items so possible combinations will be:

24 = 16; So. There are 16 possible combinations that can be made by using the above
problem. Once all the combinations are made, we have to select the combination that
provides the maximum profit.

Another approach to solve the problem is dynamic programming approach. In dynamic

programming approach, the complicated problem is divided into sub-problems, then we
find the solution of a sub-problem and the solution of the sub-problem will be used to find
the solution of a complex problem.

How this problem can be solved by using the Dynamic programming

approach?
First,

we create a matrix shown as below:

0 1 2 3 4 5 6 7 8
0
1
2
3
4
In the above matrix, columns represent the weight, i.e., 8. The rows represent the profits and
weights of items. Here we have not taken the weight 8 directly, problem is divided into sub-
problems, i.e., 0, 1, 2, 3, 4, 5, 6, 7, 8. The solution of the sub-problems would be saved in the
cells and answer to the problem would be stored in the final cell. First, we write the weights
in the ascending order and profits according to their weights shown as below:
wi = {3, 4, 5, 6}
pi = {2, 3, 4, 1}
The first row and the first column would be 0 as there is no item for w=0

0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0
2 0
3 0
4 0
When i=1, W=1

w1 = 3; Since we have only one item in the set having weight 3, but the capacity of the
knapsack is 1. We cannot fill the item of 3kg in the knapsack of capacity 1 kg so add 0 at
M[1][1] shown as below:

0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0 0
2 0
3 0
4 0

When i = 1, W = 2

w1 = 3; Since we have only one item in the set having weight 3, but the capacity of the
knapsack is 2. We cannot fill the item of 3kg in the knapsack of capacity 2 kg so add 0 at
M[1][2] shown as below:

0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0 0 0
2 0
3 0
4 0

When i=1, W=3

w1 = 3; Since we have only one item in the set having weight equal to 3, and weight of the
knapsack is also 3; therefore, we can fill the knapsack with an item of weight equal to 3. We
put profit corresponding to the weight 3, i.e., 2 at M[1][3] shown as below:
 0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0 0 0 2
2 0
3 0
4 0

When i=1, W = 4

W1 = 3; Since we have only one item in the set having weight equal to 3, and weight of the
knapsack is 4; therefore, we can fill the knapsack with an item of weight equal to 3. We put
profit corresponding to the weight 3, i.e., 2 at M[1][4] shown as below:

0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0 0 0 2 2
2 0
3 0
4 0

When i=1, W = 5

W1 = 3; Since we have only one item in the set having weight equal to 3, and weight of the
knapsack is 5; therefore, we can fill the knapsack with an item of weight equal to 3. We put
profit corresponding to the weight 3, i.e., 2 at M[1][5] shown as below:

0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0 0 0 2 2 2
2 0
3 0
4 0

When i =1, W=6

W1 = 3; Since we have only one item in the set having weight equal to 3, and weight of the
knapsack is 6; therefore, we can fill the knapsack with an item of weight equal to 3. We put
profit corresponding to the weight 3, i.e., 2 at M[1][6] shown as below:

0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0 0 0 2 2 2 2
2 0
3 0
4 0

When i=1, W = 7
W1 = 3; Since we have only one item in the set having weight equal to 3, and weight of the
knapsack is 7; therefore, we can fill the knapsack with an item of weight equal to 3. We put
profit corresponding to the weight 3, i.e., 2 at M[1][7] shown as below:

0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0 0 0 2 2 2 2 2
2 0
3 0
4 0

When i =1, W =8

W1 = 3; Since we have only one item in the set having weight equal to 3, and weight of the
knapsack is 8; therefore, we can fill the knapsack with an item of weight equal to 3. We put
profit corresponding to the weight 3, i.e., 2 at M[1][8] shown as below:

0 1 2 3 4 5 6 7 8
0 0 0 0 0 0 0 0 0 0
1 0 0 0 2 2 2 2 2 2
2 0
3 0
4 0

Now the value of 'i' gets incremented, and becomes 2.