The 0/1 Knapsack Problem (Demystifying Dynamic Programming)

are you so today we have a very exciting  problem this problem is very things it's   called the zero-one knapsack problem so this  is a very famous dynamic programming problem   we'll see why this identity dynamic programming  basically what is the question the question is   write a program that selects a subset of items  you're given that is maximal in value but stays   within a weight constraints were given here I have  an example our weight constraint is at max we can   pick five pounds worth of items and we get it I  know that's five pounds or it's $60 an item that's   three pounds worth $50 an item that's two pounds  worth $70 and an item that's one pound worth $30   so these are the items were given we're told pick  whatever subset of these items that is less than   five pounds but maximum in dollar value we want  the maximum dollars how do we do this this this is   such a tough problem like how are we gonna arrange  our subsets how do we solve each each sub-problem   does this even sub problem down first off let's  let's see why it's zero one first so zero ones   means we cannot split items we can't split items  meaning if if this were not zero one we would be   able to choose the largest item the second largest  we would first sort it which would cost us n log n   in time we pick the largest second largest third  largest until we run out of weight when we run   out weight we split the last item so that we stay  within the weight constraint and still get those   largest items this is a greedy solution this is  how you solve it greedily but we cannot split   items this is 0-1 knapsack problem meaning we  can't split items so we need to think a little   more so then second when we're told subsets we  can always do complete search complete search is   always in your toolkit whenever you're solving  any interview question we could look at all of   the subsets this would cost us I think two to the  N time well we'd have to investigate every subset   and stay within the weight strain and then of all  of those subsets within the weight constraint we   would take the subset with the maximum value this  is going to be exponential in time because we're   taking subsets and there's going to be two  to the n total subsets when we do a self set   that you all explain why that's the case this is  exponential time this is a brute force solution   we can't have exponential solution do you see  the potential to subproblem e this is why this   is dynamic programming let's see why and how this  breaks down into smaller subproblems that we know   the answer to so why is this problem dynamic  program dynamic programming is there's there's   nothing there's nothing mysterious about it it's  not about making DP tables and randomly memorizing   assignments without studying for programming  interviews I memorized the recurrence relation   for different things like levenshtein distance  and and and different problems like longest common   subsequence it's not about memorizing it's not  about tables it's about subproblems it's about   knowing the solution to a subproblem so that I  can optimize the solution to my problem that I'm   solving right now based on previous solutions  this is the whole point of dynamic programming   subproblem e and remembering the answers to our  previous work here's our example our maximum   weight is five we have four items one we have five  pound three pound for pound two pounds items and   you can see their values over there here is an  example of just this is one pathway we could take   during the solving of our problem so you can  see what I mean by subproblem so we start off   with five pounds the total weight left is five  pounds our possible choices we can choose item   one two three or four we can choose any of the  items in this first step and right now we have   zero dollars let's say I say I want to choose item  - I want item two item two is worth $50 item two   is worth $50 and is three pounds I started with  five pounds I have two pounds left I subtracted   three well can I choose now I have two pounds  left what other items are within two now when   one item that's two pounds so the only choice  I can make from here is item four and how much   value do I have I have $50 Y and $50 because I  am to the item I chose is worth $50 this is where   it's a give-and-take if we choose an item we get  its value but we lose the amount of items we can   choose we lose we get closer to that maximum  weight so that's why this is an optimization   problem where we need to know the answer to our  other sub problems that we solve this is just one   expression of one sub problem okay so now we're  gonna walk through the bottom-up approach so I'm   just describing the top-down recursive approach  where we subproblem a and fill out this table but   we're gonna walk through it bottom up to see that  way as well so at each stage each of these cells   represent a sub problem so the top sub problem we  want to solve is for a weight of five we're going   to solve up to that sub problem but what we're  going to do is we want to start from the bottom   and work our way upwards we're going to start at  answering if I have a maximum weight of zero if   I have a maximum weight of one max - max three  max four once we get to max five we will know   the optimal answer the first thing we need to  consider are what are our choices at each stage   what do each of these columns and rows represent  so in this first row I only have item one to work   with I'm asking when I'm in this cell I'm asking  if I have a max weight of three using only item   one what is the maximum weight I could get if I'm  in round three I'm saying if I think this cell   right here itself or if I have a maximum weight  of four using only items one two and three what   is the maximum weight I can get and you see how  we're building up to the final solution defining   the last cell here if I have a max weight of  five and I only can use item one two three   and four what is my answer that is our original  question that is what we are building up to but   first before we get into even filling it out and  doing a recurrence relation we need to consider   what our choices are our choice is do we use the  item in the road we're sitting in or do we not   use it so if we choose the if we choose to use the  item the I is is the rows where and the items were   considering we either can take the weight of the  previous row we can just pick what's right above   us why do we do that we take the road that's right  above us because if we don't consider this item at   all it's not gonna take away from the weight that  we're using if I can if I can use item 1 or 2 and   I have a max weight of 3 if I don't use item 2  then my stuff problem becomes only using item 1   how can I maximize my price with weight of 3 if  I don't choose item 2 item 2 is not gonna hurt   or weight but if we choose item 2 item 2 is going  to subtract from our late but is going to give us   the value that it holds so if I choose item 2 and  I'm considering this subproblem item 2 is going to   subtract 3 pounds item 2 is going to subtract 3  times 1 2 3 and we chose item 2 so then the next   sub problem becomes if I just had item 1 because  we were only considering item 1 and 2 this might   be a little confusing but this is our recurrence  of relation we have two choices to make we only   have two choices include this item or do not  include it so when we're going down our rows each   of these rows represent only considering either  one considering I didn't wanted to considering   item 1 2 3 considering item 1 2 3 and 4 at each  of those rows we can choose to not consider   or consider the item let me walk through this  they'll be become more clear as we walk through   this here's the like mathematical recurrence  relation and knows what I was just saying is   we take the maximum image if we don't choose  the item it does subtract from our weight or   we choose the item where we'd go up one row and we  subtract the weight that the item item takes away   but it contributes its value the item contributes  the value that it gives us otherwise we just take   the row above us if this item does not late and  if this item is over the weight constraint and   we can't even include it at all so an example of  where we would just take the value above us where   we couldn't even consider including this item is  if we're looking here we have the subproblem for   the max weight of two if i can consider item 1 and  2 what is the maximum weight I can get well I even   2 is 3 pounds we can't do anything with that and  it turns out I don't 1 is also 5 pounds we can't   solve for 2 pounds both of these are gonna fall  through and we're not even true they'll just end   up being 0 you'll see as we fill it out so now  that we've gone into sort of what's about it   happen let's actually fill out this table and go  through the logic of the comparisons we're going   to make to find a globally optimal solution all  right so we're in the first row are considering   our first class of subproblem so I don't want only  considering item 1 what is the maximum weight that   I what's the maximum value out again with a weight  constraint of 0 well I mean it's 0 we can't choose   any items so we put 0 the answer is 0 what can  we do if we're choosing a weight constrain of 1   and then keep in mind item 1 how much this item  one way item one weighs 5 pounds we can't answer   anything until we get to 5 how are we how are we  going to answer it for one week and one is a way   constraint we can even choose I don't want I don't  want is the only item we have so all of these just   became 0 because a subproblem for 2 max 3 max for  max it for is my maximum I can't choose item 1   it's worth 5 pounds it's never gonna work but then  it says 5 pounds if we only have item 1 and our   maximum weight that we can reach is 5 pounds well  we can choose item 1 now we can because it's worth   5 pounds so what is the value of one the value  of item one is $60 so we choose either one and   we reap $60 so now we are finished this is Row 1  this is these are answers to sup roams these cells   are not magical this is nothing magical these are  all answers to subproblems we asked ourselves six   questions here and we got six answers and in the  next row we're going to use these six answers to   further their art or progression to the global  optimal solution that is the answer that we're   looking for so now next row item one and two we're  considering item one and two and now what is the   most optimal solution we can get with zero as  our max wait we can't choose anything it's zero   what is the optimal weight we can get if we are  choosing between we have I don't want to do it   pick or leave item two if our max weight is one  well I don't choose max weight is three pounds   so I'm going to is three pounds we're never going  to get to choose it so each time we're going to   take from above us because we can't choose item  two we're gonna have to take from here take from   here but why do we do that why didn't we just take  from above us because at each stage we're making   choices the choice we made is we can't choose item  two item to subtraction nothing from our weight we   didn't choose it so we need the answer to the  proper sub problem same weight weight doesn't   change it we couldn't choose items you we need  the same we need the answer to the subproblem   above it so this is to start making a little more  sense very difficult to grasp at first but let's   keep going through so now we're at three pounds  we can consider I know to so we have the choice   between don't choose item two we can get zero  dollars don't choose item two we can get zero   dollars for a max weight of three or how much  this item two eight three one two three we go   up one row why did we just go up one row we go  up one row because we are choosing it now and we   need to see what it would be if we could also  choose I don't want so now in this we go zero   zero plus the weight beep if we took item 250 so  we just compare 50 versus zero which do we want   to choose 50 15 maximizes will be taken over the  next row now we're free to choose either - I can   choose 3 pounds passed here we can choose it so  now let's go 1 2 3 1 now we add 50 50 versus 0 50   and now we need to see so something about this 1  2 3 we're gonna be doing like that we're gonna be   doing compared don't don't memorize their pattern  think about the subproblems so so we're comparing   60 60 against 1 2 3 go up 1 this is if we choose  this 0 0 + 50 is 50 50 versus 60 if we do choose   item 2 we can get 50 dollars if we don't choose  item 2 we can get 60 dollars which do we choose   we don't choose it we don't choose item 2 we  keep $60 why because we can get $60 we can   get $60 if we just choose I don't 1 why would  we choose item - do you see these are amp we   are answering questions as we go down this table  this is not a memorizing thing where you figure   out like the formulas you're going you're thinking  about this and you're seeing what the answer is to   your subproblems as you go down alright now that  we're starting to get this let's speed things up   and start going through these a little faster so  we have we now consider item 3 we can take item 3   or we can leave item 3 item 3 is 4 pounds so what  we do is 4 pounds we're not going to be able to   consider item 3 until that sub-problem gets here  so what we're going to do is we're going to take   from the top we came and picked item 3 so we're  going to take from the top as if we didn't pick   item 3 because we can't pick item 3 so now okay  we took from the top that makes sense but now   we can choose item 3 item 3 is 4 pounds so if  we choose item 3 1 2 3 4 we chose item 3 and   subtracted foregrounds from the max weight 0 0 + 7  if we do choose item 3 we can get $70 if we don't   choose item 3 we can get $50 which are we going  to choose we're gonna choose item 3 we're gonna   take $70 now let's do that again 1 two three four  IM three four pounds we can reap $70 we can reap   $70 or we can take $60 don't choose it choose it  don't choose it choose it right $70 or $60 which   are we gonna take we're gonna take seven and  now what you see we answer it all suppose if I   consider I just I don't wanna if I consider just I  don't one and two if I consider just items one two   and three were so close to the solution now let's  solve the last row so this item is two pounds we   can't do anything here we can't do anything there  it's to balance we're always we're not going to be   able to choose it when you'll be able to choose  it we won't be able to choose it and now we have   an opportunity to optimize so let's see what it is  so this item is two pounds and it's worth thirty   so one two thirty thirty plus here is zero is  is 30 so 30 versus zero if we choose the item   we get thirty dollars don't choose to get zero  dollars so let's choose it okay so now let's do   the next one one two if we choose the item we  get zero plus thirty we get thirty dollars if   we don't choose it we get fifty dollars what do  we choose fit so let's do it again one two if we   choose the item we get zero plus $30 we get thirty  dollars versus $70 which do we choose seven okay   so now you're starting to get it and wear it the  last step or the last cell this is the problem   we want to answer we did not answer the problem  we were given we answered all of these problems   all of these subproblems we answered we did not  answer the top we answered we built up to this   answer and optimized along the way now our global  solution will be optimized so now let's go back   to 1 to 50 so this subproblem was answered with  50 so what we know is if we added item forward   now we can have 30 dollars in value so 30 dollars  in value 80 80 if we choose item forward if we do   not choose buy them for we can get 780 versus 78  so what is the answer to the question with this   the answer is 80 if we have a max weight up five  and if we can choose items one two three and four   our answer is 80 80 is the maximum value we can  get while staying within the weight constraint   and this is how dynamic programming works and this  is how the subproblems break down so a question   you might get asked is what items did we choose  what items did you choose how are we going to know   that so let's switch marker and let's look at this  table let's enough although any patterns let's not   try to trace things and follow the pattern let's  think about what we just did so here we have two   choices choose item 4 or don't choosing if we have  chosen item 4 then that means it's going to be a   it's going to be this cells value 2 over and 1  up plus 30 which is this right if we have not   chosen it it would be this value and this value  is not this value that means we did choose item   4 we do choose item 4 so yes we chose item 4 so I  before was chosen so now let's go down here let's   go back ok we chose sign before and now I know for  takes us to this subproblem subtract 2 pounds item   4 takes 2 pounds away because of a few pounds  go up 1 and now we see 50 and now that we see   50 we say hey wait is this the same value as it  is above us yes but look it's worth value 72 go   over 1 to 70 Plus this this is not this this means  we we chose to not choose this item that means we   just took this value we chose to not choose it  so skip up here because we did in 2003 and now   we're at this sub problem considering max weight  3 and items 1 into our choosable so now we have 50   do we take from above us no item if 2 is worth  50 yes we got it from here so now I am Jewish   and then now item two is chosen and then we're at  zero and then we're finished so what do we see our   optimal answer is I am to an item or so this  is the zero-one knapsack problem the thing is   how does this solution adapt for other things how  does this take translate to other problems so the   key is identified their current relation when  you get a problem that is something you could   stop problem tell your interviewer I'm looking  for the recurrence relation I'm looking for how   this can break down into subproblems you can do  this bottom up like this or you can do it top   down recursively I prefer top-down recursively  because it seems more natural because at each   point recursion is a beautiful way to express  decisions as you go downwards and go towards   your answer oh and this is going to be Big O of  n times M top cut time complexity and M times M   space or n times Waits so the N the max weight  max weight times the number of items if we call   the number of items and and we call the max weight  M so it would be n times M because as you can see   we make an n times M matrix for space and then  we would have to solve n times n subproblems so   that's why our time complexity is n times n space  at n times n but we can make the space complexity   better but we'll leave that for another day this  is the zero-one knapsack problem and this this is   dynamic programming there's no magic to it is it  very very difficult it's something that takes time   and the at your best just try to think as much  as you can very difficult problems very hard to   grasp it took me like a month to grasp this but  yeah this is zero on outside problem and yeah

Channel: Back To Back SWE

Views: 127,345

Rating: 4.8072042 out of 5

Keywords: Back To Back SWE, Software Engineering, programming, programming interviews, coding interviews, coding questions, algorithms, algorithmic thinking, Google internship, Facebook internship, software engineering internship, swe internship, big n companies, dynamic programming, 0/1 knapsack problem, knapsack problem, recursion, greedy algorithms, software engineering

Id: xCbYmUPvc2Q

Length: 20min 30sec (1230 seconds)

Published: Fri Dec 21 2018