0/1 Knapsack Problem Using Dynamic Programming || Design and Analysis of Algorithms || DAA

#sudhakaratchala #daavideos #daaplaylist
We are having ‘n’ objects and a knapsack or a bag in which the object ‘i’ has weight ‘wi’ is to be placed. And the knapsack has capacity ‘M’.
The profit pixi can be earned, if an object ‘i’ has to be placed into the knapsack.
The objective of the knapsack problem is to fill the knapsack with maximum profitable objects and the sum of the weights of the object is lessthan or equal to the capacity of the knapsack. That is

Maximize ∑2_(𝑖=0)^𝑛▒"pixi"
Purging rule (or) Dominance rule

If Si+1 contains (pj, wj) and (pk, wk) two pairs such that (pj ≤ pk ) and (wj ≥ wk)
then (pj, wj) pair can be eliminated. This purging rule is also called "dominance rule”.

In purging rule basically the dominated tuples get purged that is remove the pair with less profit and more weight.

The formula for solving the problem is

Si+1 = Si U S1i

[The_usual_dude]

Happy Teachers day sir.. without you there would be many backlogs in my btech but you made me clear all in the first attempt itself! thank you so much sir for teaching many students like us and helping them to pass their exams ❤️

[betta]

he is our telugu version of gate smashers good sir

[VINAY-wgul]

Your explanation outstanding sir. Thank you sir thank you sooo much❤

[rampandusatla]

Never understood this tricky concepts in entire sem, what a detail and clear explanation sir our exams doesn't ends with your clases .... tqqq you 😇♥you sir

[KukuluriSravani]

Sir, meeru lekapothe memu mamimun kuda pass avvamu sir, u r my real god of teacher sir ....

[allurivishnuvardhanvarma]

Happy teacher's day sir ❤️
Best teacher ever 😃

[k.venkatamuni]

Ur videos are most useful to btech students sir thank you so much sir ur videos are useful in my exams for that tq so much sir 🙏🙏🙏🙏

[bharathbunny]

Sir thankyou so much your classes are very clear and understandable 🙏

[MahendraAlla-bn]

Tomorrow is my sem exam and understand this in one time ...great explanation sir😊

[mahim]

Thankyou very much sir, many students are depending on your class videos .

[madhuhindhu]

Understood clearly thank you so much sir❤❤😊😊

[dchxmonster.]

Thank you sir for this kind of explanation❤❤❤ I hope in future our college faculty can teach like you 😢😢

[kimalice]

Thank You Sir For Your Efforts and Support. I really Appreciate it..

[harshvardhantandon]

Thank you sir this is the best explanation on YouTube thanks a lot 😊❤

[Lohitha-vj]

Thank a lot sir😇😇😇your video lectures are very helpful for And your teaching was too good

[RepublicGammer_]

every engineering faculty also refer your video and they make practice at her for next day classes

[adarinikhil]

Sir what if profits are not in order of purging rule

[veerabhadrareddy]

Thank you so much sir, your videos are very useful for many b-tech students, keep rocking sir....🤝

[Cleo]

very good and nice explanation sir thank u

[LOKESH-wskm]

Sir, if you don't mind can you explain tableisation method also