Scribd
Upload
33 views1 page

0/1 Knapsack Problem with Branch & Bound

The document discusses the 0/1 Knapsack Problem using a Branch and Bound approach with FIFO. It outlines the process of minimizing profits by treating them as negative values and calculating lower and upper bounds for various nodes. The final result indicates a maximum profit of 25 after converting the minimization problem back to maximization.

Uploaded by

nokimo3960
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
33 views1 page

0/1 Knapsack Problem with Branch & Bound

The document discusses the 0/1 Knapsack Problem using a Branch and Bound approach with FIFO. It outlines the process of minimizing profits by treating them as negative values and calculating lower and upper bounds for various nodes. The final result indicates a maximum profit of 25 after converting the minimization problem back to maximization.

Uploaded by

nokimo3960
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

0/1 KNAPSACK PROBLEM

USING FIFO

BRANCH AND BOUND


ANISH JOSHIRAO TYRLE54
ANISH JOSHIRAO TYRLE54

nodes=5, maximum capacity of knapsack


-p5 w5 2
(m)=12, profit(p1,…,p5)=(10,15,6,8,4) +
weight(w1,.….,w5)=(4,6,3,4,2) -p4 w4 4
x1 x2 x3 x4 x5
+
(2/3) 12
-p3 3
*3
TAKE ALL PROFITS AS NEGATIVE VALUE AS BRANCH AND BOUND IS A +
MINIMIZATION PROBLEM, SO TO CONVERT MAXIMIZATION PROBLEM INTO -p2 6 6
MINIMIZATION PROBLEM +
PROFITS(P1,....,P5)=(-10,-15,-6,-8.-4)
-p1 4 4
1
C= LOWER BOUND , FRACTIONS ARE ALLOWED C=-29
U= UPPER BOUND, FRACTIONS ARENT ALLOWED U=-25 = c u
NODE 1
C= -10+-15+(2/3)*-6=-29 X1=1 X1=0

2 3
U= -10+-15=-25 C=-29 C=-27
U=-25 U=-21
GLOBAL UPPER BOUND (U^)=-25

X2=1 X2=0 X2=1 X2=0

4 5 6 7
C=-29 C=-26 C=-27
U=-25 U=-24 U=-21

C=-18
X3=1 X3=0 X3=1 X3=0 X3=1 X3=0 U=-18
lower bound >
global upper

8 9 10 11 12 13
C=-29 bound
U=-25 kill the node

sum of objects> C=-26 C=-22 C=-27 C=-27


m=12 X4=1 X4=0 U=-24 U=-22 U=-21 U=-27
kill the node upper bound < global
upper bound , update
global upper bound

14 15
C=-29
U=-29 COMPARE GLOBAL UPPER BOUND WITH UPPER BOUND OF EACH
NODE, UPDATE GLOBAL UPPER BOUND IF U<U^
sum of objects>
m=12 X5=1 X5=0
kill the node
IF GLOBAL UPPER BOUND<LOWER BOUND, THEN KILL NODE

16 17
convert minimization problem into maximization problem by changing -ve
profit sign to +ve sign
C=-29 C=-25 max profit = 10 + 15 + 4
U=-29 U=-25 = 25

You might also like