0/1 Knapsack Problem using Least Cost Branch and Bound ( LCBB ) || Design and Analysis of Algorithms

#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

[akshaya]

Nyc explanation. I clearly understood just by listening for first tym itself.Thank u sir.

[gvindya]

Thank you so much for the videos sir. They are a life saver 💯💯 wouldn't have passed my COA exam without these videos

[azverndias]

Sheesh keep it up, easily understood this thanks to you. God bless you

[challaanitha]

Thank you sir .. Great explanation sir it was very understandable keep it up sir.

[uvicqwg]

Iam passed many subjects by listening u r classes only sir

[ritikakosigi]

thank you sir!!! this was the most confusing topic. the explanation was very clear

[yarramneninikhil]

We have compare lower bound know sir c^n

[rajusiddi]

Thank you so much sir your vedios are me a lot for preparation 😊

[naninaresh]

Sir, what is the difference between fifo and lcbb 0/1 knapsack problem

[sidduroy]

Great Work sir, keep doing all the best

[pavanganeshvodnala]

Thank you so much sir, for clear explanation 🎉❤

[Pgggg]

dear sir, also write the code if possible. it will help more in the explanation

[sreeshanthreddykunta]

To further explore the node should we compare the u^n or c^ n sir...

[Happysoul]

State space tree is taken upto which number

[ostrich]

Sir plzz explain travelling salesman problem in FIFO branch and bound

[guddojiramesh]

Please explain backtracking algorithms and Hamiltonian circuits

[aravinreddy]

Sir at 23:11 what if both lower bound and upper bound is same for 6th node and 7th node..?? Then which we have to choose

[makergamesop]

Guys please like the video ur waching the video one day before the exam and forget to thank the sir like the video guys it will help them

[Priya_honey_]

Explain more in Telugu sir plss avoid English 🥲🤌🏻