0-1_knapsack_using_DP, types of knapsack

knapsack_using_Dynamic programming

1. 0/1 knapsack using DP

2. 0/1 Knapsack Problem We are given a knapsack of capacity m and a set of n objects numbered 1,2,…,n . Each object i has weight w i and profit p i . Let x = [x 1 , x 2 ,…, x n ] be a solution vector in which x i = 0 if object i is not in the knapsack, and x i = 1 if it is in the knapsack. The goal is to find a subset of objects to put into the knapsack so that (that is, the objects fit into the knapsack) and is maximized (that is, the profit is maximized ).

3. 0/1 Knapsack Problem The naive method is to consider all 2 n possible subsets of the n objects and choose the one that fits into the knapsack and maximizes the profit. Let F[i,x] be the maximum profit for a knapsack of capacity x using only objects {1,2,…,i} . The DP formulation is:

4. S 1 i ={(P,W)|(P-p i+1 ,W- w i+1 ) € S i } we can compute S i+1 by merging and purging the pairs in S i and S 1 i Note :S ={(0,0)}

5. Purging - If S i+1 contains 2 pairs ( P j, W j ) and ( P k, W k ) with property that P j <= P k and W j >= W k and weight exceeds capacity of bag

6. Example n=3 m=6 (w1,w2,w3)=(2,3,4) (p1,p2,p3)= (1,2,5)

7. Object x1 x2 x3 Pi 1 2 5 Wi 2 3 4 S ={ ……….} S 1 ={ ……….} S 2 ={ ……….} S 3 ={ ……….} S 1 ={ ……….} S 1 1 ={ ……….} S 1 2 ={ ……….}

8. Object x1 x2 x3 Pi 1 2 5 Wi 2 3 4 S ={ ……….} S ={ (0,0) } S 1 ={ (1,2)} S 1 ={ ……….} S 1 ={ (0,0)(1,2)} S 1 1 ={ (2,3),(3,5)} x2 2 3 x1 1 2

9. Object x1 x2 x3 Pi 1 2 5 Wi 2 3 4 S ={ ……….} S 1 ={ (0,0)(1,2)} S 1 1 ={ (2,3),(3,5)} x2 2 3 x1 1 2 S 2 ={ ……….} S 2 ={(0,0)(1,2), (2,3),(3,5) } x3 5 4 S 1 2 ={(5,4)(6,6), (7,7),(8,9) }

10. Object x1 x2 x3 Pi 1 2 5 Wi 2 3 4 S ={ ……….} x2 2 3 x1 1 2 S 2 = {(0,0)(1,2), (2,3),(3,5) } x3 5 4 S 1 2 ={(5,4)(6,6), (7,7),(8,9) } S 3 ={ ……….} S 3 = { (0,0)(1,2), (2,3),(3,5),(5,4),(6,6),(7,7),(8,9) }

11. purging S 3 = { (0,0)(1,2),(2,3),(3,5),(5,4),(6,6),(7,7),(8,9) } Profit is less and weight is less Weight is greater than m

12. After purging S 3 = { (0,0)(1,2),(2,3),(5,4),(6,6) }

13. Trace back S ={ (0,0) } S 1 ={ (1,2)} S 1 ={ (0,0)(1,2)} S 1 1 ={ (2,3),(3,5)} S 2 ={(0,0)(1,2), (2,3),(3,5) } S 1 2 ={(5,4)(6,6), (7,7),(8,9) } S 3 = { (0,0)(1,2),(2,3),(5,4),(6,6) } X1=0 X1=1 X2=0 X2=1 X3=0 X3=1 (6,6) gives maximum Profit It came from S 1 2 So x3=1 i.e (6,6) obtained from (6-5,6-4)=(1,2) (1,2) € S 2 It came from S 1 So x2=0 (1,2) came from S 1 So x1=1

14. Solution is (x1,x2,x3) = (1,0,1)

15. Algorithm