4.5.1 0/1 Knapsack Problem (Program) - Dynamic Programming
HTML-код
- Опубликовано: 3 мар 2018
- 0/1 Knapsack Problem explained using Program
PATREON : www.patreon.com/bePatron?u=20...
Courses on Udemy
================
Java Programming
www.udemy.com/course/java-se-...
Data Structures using C and C++
www.udemy.com/course/datastru...
C++ Programming
www.udemy.com/course/cpp-deep...
You are an excellent teacher, sir. Your effort is much appreciated.
Awesome content, by far the most understandable and easy to understand. I aspire to be you when explaining a difficult topic.
I hope this AMAZING channel reachs millions of subscribers, THANKS, sirm you are awesome 🥊
Correction :
cout
@Phantom mercy It exits the inner loop so w is out of scope.
Best explanation about knapsack algorithm implementation on youtube. Thanks a lot!
No words to describe how excellent your teaching is .
Sir, you are an excellent teacher. Thanks a lot...
I can't belive how talented you are
future viewers, some things to note!!
it's important for p[0] = wt[0] = 0 to exist. in the video, p and wt already have 0 at the start. this makes the table's first row and first column filled with 0.
your implementation may need to change if your table's doesn't have that initial condition. you might see `p[i-1]` and `wt[i-1]` in other implementations, this is because the "p" and "wt" usually don't have 0 instantiated thus you shift everything over by 1 to fit the first row filled with 0 (therefore requiring you to do i-1 to index correctly).
thanks
Taught very clearly!
(Perhaps a little mistake at 15:26 ? Reducing i-- before accessing J for weight reduction would seems wrong ?)
Thanks for this brilliant teaching sir
Sr, I have no words for appreciation of your way of teaching. I can't compare it with that of any other course faculties or youtubers. Its Unique ! I am following your course also for dsa from Udemy, i have successfully completed it and it happened first time with me that I am almost 90-95% satisfied with a purchased course and that is also at easily affordable cost. Thankyou So Much for your efforts for us, Sr. I want to pay Respect to you by heart !🙏
Best video on data structure
Really an awesome video sir , please discuss like this for other algos. too!
Breakdown of the formula:
⭐K: DP table which stores values of subproblems
⭐K[i, w]: Maximum profit by considering the first 'i' elements in a bag of weight 'w'
⭐p[i]+ K[i-1, w-wt[i]]: Case when the current object is included(~1) 'p[i]' and the remaining part of the bag 'w-wt[i]' must be filled with the maximum profit possible (stored at 'i-1')
⭐K[i-1, w]: Case when the current object is not included(~0) and the bag with current weight 'w' must be filled with the maximum profit possible (stored at 'i-1')
(~ Hence the name 0/1 knapsack problem)
Pls bro, I'll like you the explain more on that of k[i-1] work without leading to error, of course I know that it is related to o base index but for example if we have a loop like this
String hold="" ;
for(int i=0; i
omg thank you so much!
Thhank you teacher for this lesson and the previous one concrning the knapsack problem it is really well understood and well explained
superb adn simple ,.happy to see your vieos ,
Thanks Sir! Your explanations never disappoint
I have now understood the meaning of the universe, the key to everything... but I cannot explain it (or give it) to you. You have to find it by yourself...
lol
you are just amazing sir as i have problem in english but i understood you explanation you are simply great sir
thank you so much sir
🙏🙏🙏🙏
This code is stuck in my mind from the way you explained thanks for taking so much efforts for us God bless uhh 🙏
I just purchased your C++ Programming!!!
Best explanation,ever!!!
Dear Sir Great work just these words i can say thanks alot
fantastic. Respect from Azerbaijan
You are an amazing teacher
You 're really Great Sir
good teacher is very small word for you sir!
Thank you very much. You are a genius. 👍👍👌👌🔝🔝🙏🙏
Ma sha Allah sir.... May Allah bless you!
sir please do videos on approximation and randomization algorithms
last line " cout
thanks, you are good teacher
Thank you sir, been following your videos for DAA and they're very helpful! I had a doubt, I'm not able to understand why 0/1 knapsack has exponential complexity, looking at the code it seems the program has O(n*m) complexity..
you can think like generating the all the subsets of a set
Its also a possibility but complexity which we consider is worst case. So worst case complexity O(n*n)
Using dynamic programming, we may not call again functions for small values and take them immediately from a two-dimensional array and therefore the complexity is O (n * w), but if we called functions recursively, then the complexity would be O (2 ^ n)
Abdul Bari = GOD of DSA
thanks a lot again for sharing gem of a video for us
Excellent explanation. Thanks very much. One question - the "cout
You should put K[i][w] , and then a break line out of the loop , that way you get the table
0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1
0 0 1 2 2 3 3 3 3
0 0 1 2 5 5 6 7 7
0 0 1 2 5 6 6 7 8
Like this
#include
#define objects 4
#define capacity 8
using namespace std;
int max(int a, int b) {
if(a>b) {
return a;
}
return b;
}
int main() {
int Profit[objects+1] = {0,1,2,5,6};
int Weight[objects+1] = {0,2,3,4,5};
int Table[objects+1][capacity+1];
cout
@@xarenwoPls bro, I'll like you the explain more on that of Table[i-1] work without leading to error, of course I know that it is related to o base index but for example if we have a loop like this
String hold="" ;
for(int i=0; i
Thank you for your efforts
best explanation thanks
WOW........my god... too easy to understand here...
very nice explanation sir, Thank you ! :)
there is small error in the code at 15:11 first we have to write j=j-wt[i] then i=i-1;
can you please explain why it is an error?
@@KeyMajorSiddharth we want the weight of ith object for j=j-wt[i] so if you decrement i first it will point to i-1 object
please watch this playlist for detailed explanation of dynamic programming..ruclips.net/p/PLeF0b8iqbx4mTBJZ5ukIYj92_B4k2L1-8..
remember that sir has made all the first elements of both the array as zero..so the previous element will point to zero..so he has used this logic..for that equation..
@@AhamedKabeer-wn1jb no bro I think it still gives an error
Sir, you have legendary white board brush hands
Please give example for Advance data structure like:-kruskals algo,prims algo etc
Thank You Sir.You are awesome
on 15:02
It should be
cout
superb bro
and also j>=0 at 15:53
Awesome explanation sir....
THANK YOU SO SIR..WELL EXPLAINED ..
thank you so much. I wish I would be your student. I am preparing for exam and I cant find knapsack problem with repetitions. I cant watch others videos, cause they arent so interesting.
Thanks a lot for the clear explanation, sir!
1 thing I found out -
While finding which object to be included at 15:30
the statements should be in this order j = j - wt[i]; i--;
and not reverse, which will give an incorrect result.
thank you so much sir
// return max profit and list of selected weights
function knapsack({ profits, weights, capacity, n }) {
// calculate and generate capacity / item table - the value of each unit will be maximum profit.
// add one item at a time and calculate maximum profit per capacity
// row: number of items -> n + 1
// col: maximum capacity -> capacity + 1
// NOTE: add one extra row and col and keep the all 0, this will help us with dynamic programming formula
let ic = new Array(n + 1).fill(0).map(row => new Array(capacity + 1).fill(0));
// ignore the first row and col
// iterate over all items - rows
for (let i = 1; i
Excellent teaching
Godfather of DS & Algo.
He teaches how to mug up things in effective way. Even you don't know how the formula derived
Wherever I go... Always come here to find final answer
its wt[ i-1 ] not wt [i ] becausearray indexing at 0 onwards
Sir last m cout
Thank you man
15:34 j should be updated before decrementing i ,or else it will substract weight of previous i
@5.00 why we are comparing index value with weights
Gurudev 🗿👑
thank you sir
sir, please make a video on coin change problem, Dynamic Programming
is it possible to combine greedy knapsack algorithm and dynamic programming in solving 0/1 knapsack problem? just to make it more efficient...
My doubt is if the weight is included then we take Max function anyways the first parameter is always greater than second parameter so we always get max from the first parameter only why we take second parameter too....
I guess the order of both the solutions is O(n^2). The good news is that we came down from O(2^n) by discarding unnecessary combinations.,
what happen if we have weight like 15,10,9,5 and m=8.....how can we make the table as our weight is so larger as compared to our items
In object included logic in else part i- - shoud be after j=j-wt[] condition so that i value changes after calculation of its weight i.e. of 8-5
Thanks for the great explanation. I have one doubt, if for a given object weight=0 and profit>0 does this program include it in the bag?
Can we calculate something like ProfitDensity which will be profit divided by weight? Then sort items by profit density (dsc), weight (asc). Then pick up the items in order as long as there is space in the bag? Do you think this approach will give us the correct answer?
@@abdul_bari Thank you sir, for responding. I had to do something very similar in a test program. I don't think I got it right in that test. But later I had this idea that I could have calculated Profit Density. Can you please tell if the answer with that approach will be correct or not? Even though it will be a different problem.
@@AmitKumar-qh1ts No that will not guarantee the correct answer in all cases
Sir i guess j=j-wt[i] will be before i--?
hi Sir I have taken your Udemy courses they were pretty worthy and more than what a normal Indian student expect, thank you so much, and I have created a course on computer graphics where I got $50 till now it has been just 50 days I have activated pioneer and Paypal but Im not getting a proper way how to deposit my earning to my bank account as it is not showing any such option, also I want to know what does Udemy organic purchase exactly mean if you will help me I will be grateful to you
You should link you Payoneer account in udemy payments.
Sir I didn't understand from cout
Without getting too technical, "cout
Is it necessary here that profit and weights have to be increasing order ?
no it is not. calculate by yourself for better understanding
Sir please make video on solving this problem by set method also🙏
The order should be
j-= wt[i]
i--;
thank you very helpful
Abdul Bari! You are an excellent teacher. I think there is a bug in your reconstruction logic. I think if you decrement i before assigning j to wt[i] you will get an invalid optimal solution. I think you want to say j-= wt[i--]. If I am wrong, let me know, as that effects my understanding of the algorithm. :-) Thank you for so many thorough explanations of so many important topics.
Thanks brother. I was having this issue for a long time and couldn't figure out what was the problem. Now i understood why was the answer wrong.
I believe that’s a debugging process and not an explanation. As a summary, what’s the core idea behind all these manipulations? Who knows.. But code’s important! And here’s the code! Brilliant.
he explained the logic in previous video. which he says in the beginning of this video.
sir plz explain an algorithm for sets method
I don't think using else was good because it will make the code vague. Also, at the last part, the while loop won't execute because it's ( I = 1 and j = 0) so the last object is not checked? So we need to use 'OR' right because it will be always true (true OR false) = true so the loop continues, and when both false the loop stops
Pls bro, I'll like you the explain more on that of k[i-1] work without leading to error, of course I know that it is related to o base index but for example if we have a loop like this
String hold="" ;
for(int i=0; i
I faced an error with 2nd given else if condition and after debugging this line works fine for me.
k[i][j] = maxFunction(p[i - 1] + k[i - 1][j - wt[i - 1]], k[i - 1][j]);
in the previous video you have done"8-6=2" and search for 2 in previous row but now why are we not using that method?
Thank you Sir, great explanation. Anyway, Can you give us trick to come up with mathematical equation above like k[i][w] = max(p[i]+l[i-1][w-w[i], k[i-1][w]) ? I seem to understand the problem, but in an isolated environment, I couldn't come up with a logical formula.
well i am beginner in programming and havent solved much of DP problems till now but can say , as of DP paradigm we see to achieve current step's optimisation , we compare and pick among prev step optimised solution and any prev solution part with current step addition, so here we apply max on these two ,1st prev step optimised version k[i-1][w] and current version is k[i-1][w-w[i]] + p[i] ,so here we are comparing with similar scenario thats why taking case from prev row and here k[i-1][w-w[i]] we are checking for rest of weight w-w[i] optimised part from prev solution with addition to the profit we are getting inn current state i.e. p[i]
so thats what i think till now approach are being implemented
Hllo sir ,
Can u tell me how k[2][4]=2;
When i am calculating i am getting 3 in place of 2.Please check my problem .
I guess you would have rectified your problem but if not lemme help you out
k[2][4] so item = i = 2, j = 4 column num i.e. instance or part of sack of total wt = 8,
for item i = 2 weight is 3 (from above w[i] array ) basically weight for item 2 is 3 , as we check 3 less than j= 4 so we traverse case 2 ,
k[i][j] = max( p[i] + k[i-1][j-w[i] ] , k[i-1][j] ) i am using j instead of w in the table , to avoid the confusion of the w in above array of w[i]
so i-1 = 1 , j-w[2] = 4-3 = 1, p[i] = 2, j = 4
so k[i-1][j-w[i] ] = k[1][1] = 0, p[i] = 2 hence p[i] + k[i-1][j-w[i] ] = 2 and k[i-1][j] = k[1][4] = 1
so as you see out of these two parts (2 and 1 ) max is 2 so the result or value of k[2][4] = 2
i am sure you would have been confused by the fact of using w in both places so use j in the loop pr table instead of w.
Should not that I be n-1 and has m-1
Because n=5 and m=9
But we want K[4][8]
Hi, I so much enjoyed your tutor but I'll like you the explain more on how that of k[i-1] work without leading to error, of course I know that it is related to o base index but for example if we have a loop like this
String hold="" ;
for(int i=0; i
the first "if" statement checks if either "i" or "w" equals to 0. there won't be a case where i-1 is negative because "i" won't be 0 due to the first check.
bug in ur code while(i>0 && j>=0)
update j=j-wt[i] before i- - in else condition otherwise the output will be wrong
thanks bro
Thanks a lot for the explanation sir! But I tried the code with wt: {2,3,7}; profit: {15,90,160}; & max weight allowed 20. I got 0 as result. Logically solving the problem, since 20 is allowed, we can take 6 of 3 weight (6 * 90) and 1 of 2 weight (which gives 15), so max profit allowed is 540 + 15 = 555. I tried the below code:
#include
int max(int a, int b) { return (a > b)? a : b; }
int main()
{
// int p[] = {0,1,2,5,6};
// int wt[] = {0,2,3,4,5};
int p[] = {15,90,160};
int wt[] = {2,3,7};
int m = 20;
int n = 4;
int K[5][9];
for (int i = 0; i
The first values of vectors p and wt have to be zero. So, you have to use the following: p[] = {0, 15, 90, 160} and wt[] = {0, 2, 3, 7}
Also
int n = 3;
int K[4][21];
Moreover, you can only take zero or one of every object. Hence the name 0/1 knapsack problem.
his voice is similar to anil kumble
The explanation is Awesome. Need to know what if the weight is 100 ,223 ,345,4198 & profit is 100,200,350,1000. How to handle that? any condition is missing?
Yes, maximum capacity of bag
is it a top-down approach because of the filling the table or traversing the table from last element?
One Doubt in the tracing part
in else part,
i - - should be after j=j-wt[i]
isn't it??
Best speed (optimal) - 1.75x
What if one element can be put twice inside a knapsack
we consider only a single quantity of each element.
site is under construction sir???
your c++ link is not working
Sir,can you pls do a video for computing binomial coefficient?
god!💐
Sir i-- should be after j=j-w[i];
yes bro
there is a small error Those who are implementing it will know
at 15:52 i>0 and j>=0
yess sirrrr !! thanks for the correction