Explain 0/1 Knapsack Problem with example.

Question: Explain 0/1 Knapsack Problem with example.

March 18, 2018 Rajnish Kumar

March 18, 2018 Rajnish Kumar

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: fi(yj)=maxfi−1(y),fi−1(y−wi)+pi$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(yj)$p=f(y_j)$and w=yj$w=y_j$
4. Initially S0=(0,0)$S^0=(0,0)$
5. Then Si1=(P,W)|(P–pi,W–wi)Si$S_1^i=(P,W)|(P–p_i,W–w_i)S_i$
6. Si+11$S_1^{i+1}$ can be computed by merging Si  and  Si1$S^{i}and{S}_1^i$
7. This is used for obtaining optimal solution.

Example: Solve knapsack instance M =8 and N = 4. Let Pi=  and  Wi$P_i=and{W}_i$ are as shown below.

i	Pi$P_i$	Wi$W_i$
1	1	2
2	2	3
3	5	4
4	6	5

Solution:

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

Initially S0=(0,0)$S^0=(0,0)$

S01=(1,2)$S_1^0=(1,2)$

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

NowS1=MergeS0andS01=(0,0),(1,2)S11={Select next pair (P, W) and add it with S1}=(2,3),(2+0,3+0),(2+1,3+2)=(2,3),(3,5)since Repetition of (2, 3) is avoided.$$\begin{gathered} Now{S}^1=Merge{S}^{0}and{S}_1^0 \\ =(0,0),(1,2) \\ {S}_1^1=\text{{Select next pair (P, W) and add it with S1}} \\ =(2,3),(2+0,3+0),(2+1,3+2) \\ =(2,3),(3,5)\text{since Repetition of (2, 3) is avoided}. \end{gathered}$$

S2=MergeS1andS11=(0,0),(1,2),(2,3),(3,5)S21={Select next pair (P, W) and add it with S2}=(5,4),(6,6),(7,7),(8,9)$$\begin{gathered} S2=MergeS1andS11 \\ =(0,0),(1,2),(2,3),(3,5) \\ S21=\text{{Select next pair (P, W) and add it with S2}} \\ =(5,4),(6,6),(7,7),(8,9) \end{gathered}$$

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

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

S31={Select next pair (P, W) and add it with S3}=(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)$$\begin{gathered} S_1^3=\text{{Select next pair (P, W) and add it with S3}} \\ =(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) \end{gathered}$$

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

---

Content

• Search
• Users
• Tags
• Badges

Help

• About
• Contact
• Refund
• Policy

Site

• Publications
• Advertise
• RSS
• Sta