1. Knapsack problem is also called as rucksack problem.
2. It is a problem in combinatorial optimization.
3. Knapsack problem states that: Given a set of items, each with a mass 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.

4. There are two versions of the problem:

   a. 0/1 Knapsack Problem: Items are indivisible; you either take an item or not. Some special instances can be solved with dynamic programming.

   b. Fractional knapsack problem: Items are divisible; you can take any fraction of an item.

0/1 Knapsack Problem:

i. In 0/1 Knapsack problem, items can be entirely accepted or rejected.

ii. Given a knapsack with maximum capacity W, and a set S consisting of n items.

iii. Each item i has some weight wiand benefit value bi(all wiand W are integer values).

iv. The problem is how to pack the knapsack to achieve maximum total value of packed items.

v. For solving the knapsack problem we can generate the sequence of decisions in order to obtain the optimum selection.

vi. Let Xn be the optimum sequence and there are two instances {Xn} and {Xn-1, Xn-2… X1}.

vii. So from {Xn-1, Xn-2… X1} we will choose the optimum sequence with respect to Xn.

viii. The remaining set should fulfill the condition of filling Knapsack of capacity W with maximum profit.

ix. Thus, 0/1 Knapsack problem is solved using the principle of optimality

To solve this problem using dynamic programming method we will perform following steps:

Steps:

1. Let, fi (yj)be the value of optimal solution.
2. Using formula: $f_i (y_j) = max {f_{i-1}(y), f_{i-1}(y-w_i) + p_i}$ to solve problem.
3. Then Si is a pair (p, w) where $p = f(y_j)$ and $w = y_j$
4. Initially $S^0 = {(0, 0)}$
5. Then $S^i_1 = {(P, W)| (P – p_i, W – w_i) S_i}$
6. $S^{i+1}_1$ can be computed by merging $S^i \ \ and \ \ S^i_1$
7. This is used for obtaining optimal solution.

Example: Solve knapsack instance M =8 and N = 4. Let $P_i = \ \ and \ \ W_i$ are as shown below.

Solution:

Build sequence of decision $S^0, S^1, S^2$.

Initially $S^0 = {(0, 0)}$

$S^0_1 = {(1, 2)}$

This means while building S01 we select the next $i^{th}$ pair. For $S^0_1$ we have selected first (P, W) pair which is (1, 2).

$Now S^1 = {Merge S^0 and S^0_1} \\ \hspace{1.3cm}= {(0, 0), (1, 2)} \\ S^1_1 \hspace{0.8cm}= \text{{Select next pair (P, W) and add it with S1}} \\ \hspace{1.3cm}= {(2, 3), (2+0, 3+0), (2+1, 3+2)} \\ \hspace{1.3cm}= {(2, 3), (3, 5)} \hspace{5cm} \text{since Repetition of (2, 3) is avoided}.$

$S2 = {Merge S1 and S11} \\ \hspace{0.5cm}= {(0, 0), (1, 2), (2, 3), (3, 5)} \\ S21 = \text{{Select next pair (P, W) and add it with S2}} \\ \hspace{0.7cm}= {(5, 4), (6, 6), (7, 7), (8, 9)}$

$S3 = \text{{Merge S2 and S21}} \\ S3 = {(0, 0), (1, 2), (2, 3), (5, 4), (6, 6), (7, 7), (8, 9)}$

Note that the pair (3, 5) is purged from $S^3$. This is because, let us assume $(P_j, W_j) = (3, 5) and (P_k, W_k) = (5, 4)$, Here $P_j ≤ P_k$ and $W_j \gt W_k$ is true hence we will eliminate pair $(P_j, W_j)$ i.e (3, 5) from $S_3$

$S^3_1 = \text{{Select next pair (P, W) and add it with S3}} \\ \hspace{0.5cm}= {(6, 5), (7, 7), (8, 8), (11, 9), (12, 11), (13, 12), (14, 14)} \\ S4 = {(0, 0), (1, 2), (2, 3), (5, 4), (6, 6), (7, 7), (8, 9), (6, 5), (7, 7), (8, 8), (11, 9), (12, 11), (13, 12), (14, 14)}$

Now we are interested in M =8. We get pair (8, 8) in $S^4$. Hence we will set $X_4 = 1$. Now we select next object $(P – P_4)$ and $(W – W_4)$ i.e (8 - 6) and (8 - 5). i.e (2, 3) Pair (2, 3) € $S^2$ hence set $X_2 = 1$. So we get the final solution as (0, 1, 0, 1)