#sudhakaratchala #daavideos #daaplaylist
In 0/1 knapsack problem. We define upper(the global variable) and c’(x) and u(x) for each node.
c’(x) is the used to find the cost of the node(or effort) starting from the root.
In 0/1 knapsack c’(x) means the maximum profit at that node(with fractions ).
u(x) is used to find an improved upper bound value.
In 0/1 knapsack u(x) means the maximum profit at that node (without fractions).
After the E-node is expanded
It generates a list of live nodes
c’(x) and u(x) is calculated for each generated live node.
If an improved u(x) is generated for any newly generated live node then, update upper to u(x).
Kill the nodes whose c’(x) is greater than upper(updated)
The selection of next E-node is depends on the approach used.
LC BB – selects whose live nodes cost is least
FIFO BB – selects from next live node from the queue
LIFO BB- selects from next live node from the stack
