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

Рет қаралды 94,580

2 жыл бұрын

#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

Пікірлер: 61

@akshaya5919 2 жыл бұрын

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

@SudhakarAtchala 2 жыл бұрын

Glad to hear that. Plz subscribe to the channel and if possible share with your friends. Thanks in advance.

@gvindya8488 2 жыл бұрын

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

@SudhakarAtchala 2 жыл бұрын

Welcome vindya. Plz subscribe to the channel and if possible share with your friends. Thanks in advance.

@azverndias913 Жыл бұрын

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

@SudhakarAtchala Жыл бұрын

Most welcome. Plz subscribe to the channel and if possible share with your friends. Thanks in advance..

@challaanitha8834 2 жыл бұрын

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

@SudhakarAtchala 2 жыл бұрын

Welcome. Plz subscribe to the channel and if possible share with your friends. Thanks in advance.

@sidduroy9150 2 жыл бұрын

Great Work sir, keep doing all the best

@SudhakarAtchala 2 жыл бұрын

Thanks a lot. Plz subscribe to the channel and if possible share with your friends. Thanks in advance.

@pavanganeshvodnala2550 Жыл бұрын

Thank you so much sir,for clear explanation 🎉❤

@SudhakarAtchala Жыл бұрын

Always welcome. Plz subscribe to the channel and if possible share with your friends. Thanks in advance..

@ritikakosigi9176 10 ай бұрын

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

@SudhakarAtchala 10 ай бұрын

Glad to hear that. Plz subscribe to the channel and if possible share with your friends. Thanks in advance..

@user-uv1ic3qw4g Жыл бұрын

Iam passed many subjects by listening u r classes only sir

@SudhakarAtchala Жыл бұрын

Congratulations. Plz subscribe to the channel and if possible share with your friends. Thanks in advance..

@bhargav5611 Жыл бұрын

Nice explanation sir thank you

@SudhakarAtchala Жыл бұрын

Welcome. Plz subscribe to the channel and if possible share with your friends. Thanks in advance.

@user-uv1ic3qw4g Жыл бұрын

U r explaination is good sir

@SudhakarAtchala Жыл бұрын

Thanks. Plz subscribe to the channel and if possible share with your friends. Thanks in advance..

@rajusiddi5726 5 ай бұрын

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

@SudhakarAtchala 5 ай бұрын

All the best. Plz subscribe to the channel and if possible share with your friends. Thanks in advance...

@yarramneninikhil1299 2 жыл бұрын

We have compare lower bound know sir c^n

@user-um1el4ws7u Жыл бұрын

Thank you sir😊

@SudhakarAtchala Жыл бұрын

Most welcome. Plz subscribe to the channel and if possible share with your friends. Thanks in advance..

@user-ml8fq8yd5o 7 ай бұрын

Thank u sooo much sir...

@SudhakarAtchala 7 ай бұрын

Most welcome. Plz subscribe to the channel and if possible share with your friends. Thanks in advance..

@makergamesop 10 ай бұрын

And Thank u so much sir ❤

@SudhakarAtchala 10 ай бұрын

You are most welcome.

@trsk Жыл бұрын

Thank you sir....

@SudhakarAtchala Жыл бұрын

Most welcome. Plz subscribe to the channel and if possible share with your friends. Thanks in advance..

@silentxmoon867 Жыл бұрын

thank you sir

@SudhakarAtchala Жыл бұрын

Most welcome. Plz subscribe to the channel and if possible share with your friends. Thanks in advance..

@Phaniiiiiiiii1614 Жыл бұрын

Sir nice explanation

@SudhakarAtchala Жыл бұрын

Thanks and welcome. Plz subscribe to the channel and if possible share with your friends. Thanks in advance..

@althafbashamohammad7551 19 сағат бұрын

Thank you sooo much sir

@SudhakarAtchala 3 сағат бұрын

Most welcome. Plz subscribe to the channel and if possible share with your friends. Thanks in advance.

@BhavyasriVangala-yk9ue 4 ай бұрын

Superb explanation 🤌🥳

@SudhakarAtchala 3 ай бұрын

Thanks. Plz subscribe to the channel and if possible share with your friends. Thanks in advance..

@rengarajansrinivasan4356 Жыл бұрын

Thanks a ton sir!!!

@SudhakarAtchala Жыл бұрын

Welcome. Plz subscribe to the channel and if possible share with your friends. Thanks in advance.

@Pgggg 2 жыл бұрын

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

@SudhakarAtchala 2 жыл бұрын

In future definitely I will upload a video on algorithm but now because of lack of time I am unable to focus on code.

@adityadeshmukh5844 7 ай бұрын

Thank you sir👍.tomorrow is my exam

@SudhakarAtchala 7 ай бұрын

All the best. Plz subscribe to the channel and if possible share with your friends. Thanks in advance..

@ostrich1233 2 жыл бұрын

Sir plzz explain travelling salesman problem in FIFO branch and bound

@SudhakarAtchala 2 жыл бұрын

Ya sure. Plz subscribe to the channel and if possible share with your friends. Thanks in advance.

@ostrich1233 2 жыл бұрын

@@SudhakarAtchala already subscribed sir. Sir can u plzz explain implementing L attributed sdd . U explained entire chapter but didn't explain that topic. N i can't understand any others explanation..

@guddojiramesh3667 11 ай бұрын

Please explain backtracking algorithms and Hamiltonian circuits

@SudhakarAtchala 11 ай бұрын

Refer to the daa playlist once, kzfaq.info/sun/PLXj4XH7LcRfAG09GbFgMOLACfvbMplHsW

@sreeshanthreddykunta Жыл бұрын

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

@Oneman5333 Жыл бұрын

C^n

@naninaresh7219 11 ай бұрын

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

@SudhakarAtchala 11 ай бұрын

Fifo doesn't guarantee optimal sol where as lcbb guarantees optimal sol. Plz subscribe to the channel and if possible share with your friends. Thanks in advance..

@makergamesop 10 ай бұрын

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

@SudhakarAtchala 10 ай бұрын

So nice of you ❤️