1 of 6

0/1 Knapsack Problem

  • Consider the instance: M = 15, n = 4, (P1, P2, P3, P4) = (10, 10, 12, 18) and (w1, w2, w3, w4) = ( 2, 4, 6, 9). 0/1 knapsack problem can be solved by using branch and bound technique. In this problem we will calculate lower bound and upper bound for each node.

Amity School of Engineering & Technology

2 of 6

  • Place first item in knapsack. Remaining weight of knapsack is 15 – 2 = 13. Place next item w2 in knapsack and the remaining weight of knapsack is 13 – 4 = 9. Place next item w3 in knapsack then the remaining weight of knapsack is 9 – 6 = 3. No fractions are allowed in calculation of upper bound so w4 cannot be placed in knapsack. Profit = P1 + P2 + P3 = 10 + 10 + 12 So, Upper bound = 32

Amity School of Engineering & Technology

3 of 6

  • To calculate lower bound we can place w4 in knapsack since fractions are allowed in calculation of lower bound. Lower bound = 10 + 10 + 12 + ( (3/9)) X 18) = 32 + 6 = 38

Amity School of Engineering & Technology

4 of 6

Knapsack problem is maximization problem but branch and bound technique is applicable for only minimization problems. In order to convert maximization problem into minimization problem we have to take negative sign for upper bound and lower bound. Therefore, Upper bound (U) = -32 Lower bound (L) = -38

Amity School of Engineering & Technology

5 of 6

Amity School of Engineering & Technology

6 of 6

Consider the path from

1-> 2 ->4 -> 7 -> 8

X1 = 1 ,X2 = 1, X3 = 0, X4 = 1

The solution for 0/1 Knapsack problem is (x1, x2, x3, x4) = (1, 1, 0, 1)

Maximum profit is: = 10 x 1 + 10 x 1 + 12 x 0 + 18 x 1 = 10 + 10 + 18 = 38.

Amity School of Engineering & Technology