1 00:00:01,690 --> 00:00:07,240 OK, so now we can get on to the coding portion of this knapsack problem. 2 00:00:08,080 --> 00:00:12,010 You can see that I've already included a few function prototypes here. 3 00:00:12,520 --> 00:00:15,170 I just kind of wanted to put this to start out with. 4 00:00:16,540 --> 00:00:20,050 Wasn't trying to write too much without explaining it. 5 00:00:20,050 --> 00:00:23,560 So I just kind of go over that right now. 6 00:00:23,570 --> 00:00:26,290 But these are just some things that we know we're going to need. 7 00:00:27,580 --> 00:00:37,840 So primarily, this is our dynamic programming function right here, and it is going to return our optimal 8 00:00:38,110 --> 00:00:39,100 value. 9 00:00:39,220 --> 00:00:46,720 So the maximum value we can get out of the optimal combination of items for the knapsack. 10 00:00:48,010 --> 00:00:50,610 And so we have some arguments here that'll go to it. 11 00:00:50,620 --> 00:00:52,990 One will be definitely the list of the items, right? 12 00:00:54,190 --> 00:01:01,030 This is not 100 percent necessary because it's just the size of the like, the number of items, basically, 13 00:01:01,030 --> 00:01:02,890 which I could just reference items our size. 14 00:01:03,190 --> 00:01:09,580 But I wanted to explicitly put it in here just so it's more like clear for you guys. 15 00:01:09,580 --> 00:01:14,110 So I added that there, even though it's kind of redundant, you can just do items size if you want. 16 00:01:14,110 --> 00:01:16,750 But this is cap. 17 00:01:17,140 --> 00:01:19,510 This is the capacity of our knapsack. 18 00:01:19,630 --> 00:01:21,040 So maximum capacity. 19 00:01:22,220 --> 00:01:26,660 And then, of course, I have the dynamic programming table passed by reference, which I will be initializing 20 00:01:27,140 --> 00:01:28,250 and sending to the function. 21 00:01:29,270 --> 00:01:36,320 This function down here just returns the list of items that we ended up using for our optimal combination. 22 00:01:36,320 --> 00:01:41,330 So this is that backtracking part they were talking about in the last lecture when we started at the 23 00:01:41,330 --> 00:01:46,490 bottom right of the table and worked our way back to try and figure out what items we actually used. 24 00:01:47,090 --> 00:01:52,010 It takes the same exact parameters, and I'll give it to explain that function more once we implement 25 00:01:52,010 --> 00:01:52,160 it. 26 00:01:53,000 --> 00:01:54,950 This max function, I added right here. 27 00:01:54,980 --> 00:01:59,540 That's just something that we're going to want to use because you know that we have to look at the maximum 28 00:01:59,840 --> 00:02:07,040 between that result of the up and left cell with our value like that, some result and compared to the 29 00:02:07,040 --> 00:02:09,230 value directly above us in the table. 30 00:02:10,160 --> 00:02:16,610 So that's the reason we want this max function just so it can be a little more kind of divvied up between 31 00:02:16,610 --> 00:02:20,040 functions instead of just throwing that logic in here. 32 00:02:20,060 --> 00:02:21,950 So I chose to put that totally up to you. 33 00:02:21,960 --> 00:02:22,850 You can do whatever you want. 34 00:02:24,020 --> 00:02:31,580 So let's go ahead and just kind of get our items situated in our knapsack capacity, all the input and 35 00:02:31,580 --> 00:02:32,010 everything. 36 00:02:32,030 --> 00:02:39,830 I'm going to go ahead and just roll with the greedy method example just so we can kind of contrast how 37 00:02:39,830 --> 00:02:42,850 our dynamic programming actually gets the optimal solution. 38 00:02:42,860 --> 00:02:48,080 So if you remember from the last lecture, if you want to check that out to your memory, I kind of 39 00:02:48,080 --> 00:02:48,890 have it right here. 40 00:02:48,890 --> 00:02:51,890 But you know, some notes from that. 41 00:02:51,890 --> 00:02:59,000 But it was like a capacity of six, and it was that one where greedy method chose the value of 14, 42 00:02:59,000 --> 00:03:00,490 but it was actually supposed to be 18. 43 00:03:00,500 --> 00:03:06,350 So we're going to roll with that so we can show how the dynamic programming actually gets us the correct 44 00:03:06,350 --> 00:03:07,100 answer for that. 45 00:03:08,630 --> 00:03:15,320 So to start off, I'm just going to do an end, which is knapsack capacity, and that'll be equal to 46 00:03:15,320 --> 00:03:16,010 six. 47 00:03:16,820 --> 00:03:21,230 Then I'm going to make a vector actually do this right here. 48 00:03:21,240 --> 00:03:22,040 I'll copy this. 49 00:03:22,040 --> 00:03:28,910 We're going to make our items so I can just put that right here and I'm putting in like, I'm not using 50 00:03:28,910 --> 00:03:31,130 the standard namespace up here. 51 00:03:33,290 --> 00:03:34,310 I normally do. 52 00:03:34,430 --> 00:03:40,700 Some people kind of don't like when I do that, sometimes in videos, just because it's bad. 53 00:03:40,700 --> 00:03:42,410 Programming practice a lot of time. 54 00:03:42,410 --> 00:03:48,020 But I think, you know, if you're just doing like a small little program like this doesn't do any harm. 55 00:03:48,020 --> 00:03:53,150 But I do understand that it's not necessarily the best practice to use that. 56 00:03:53,150 --> 00:04:00,210 So I don't know in today's lecture, I'm just going to not use that, and I'm just going to put in a 57 00:04:00,230 --> 00:04:05,030 line before everything that is from that standard library. 58 00:04:05,030 --> 00:04:11,900 So yeah, you can certainly include the using namespace statement above, if you like. 59 00:04:13,190 --> 00:04:14,720 So we're just going to harkov this. 60 00:04:14,720 --> 00:04:20,240 And since we're using C++ 11 and above, we can do this. 61 00:04:21,080 --> 00:04:27,470 So this was our list of items there, just the 2D vector as pairs. 62 00:04:28,370 --> 00:04:37,220 So the first one and each pair is the weight and the second number, and each pair is the value. 63 00:04:38,090 --> 00:04:41,060 So I'm just referencing a note that I had it told me what? 64 00:04:41,060 --> 00:04:45,560 I had four values in the last lecture. 65 00:04:46,970 --> 00:04:47,540 Here we go. 66 00:04:48,380 --> 00:04:52,340 So then we're also going to want to do a table. 67 00:04:53,600 --> 00:05:01,850 So this table is going to be initialized to item size plus one. 68 00:05:02,070 --> 00:05:04,070 And OK, and this is something that is. 69 00:05:06,240 --> 00:05:14,610 Important so this is the number of rows, and we're doing a plus one because the table we're going to 70 00:05:14,610 --> 00:05:15,660 leave like this. 71 00:05:16,780 --> 00:05:17,170 Right. 72 00:05:17,530 --> 00:05:18,980 This first item in the table. 73 00:05:19,900 --> 00:05:22,180 This is technically indexed zero, right? 74 00:05:22,870 --> 00:05:25,750 So indexed zero index one. 75 00:05:26,230 --> 00:05:28,360 The thing is though, is it in our table? 76 00:05:29,140 --> 00:05:33,550 We're also going to start at index zero like we'll have a row column. 77 00:05:34,200 --> 00:05:34,540 I'm sorry. 78 00:05:34,570 --> 00:05:36,850 We'll have a row zero and a column zero. 79 00:05:37,790 --> 00:05:44,690 Except this first item is going to correspond to row one in our table. 80 00:05:45,850 --> 00:05:50,830 If you remember from the last lecture, I started with the first rule being item one. 81 00:05:51,640 --> 00:05:57,880 But I did mention that when we implement to encode that it might look different, we might have like 82 00:05:57,880 --> 00:06:01,120 a rose zero and we're going to have a real zero and a column zero. 83 00:06:01,120 --> 00:06:05,800 In the last lecture, I had to call them zero, but I didn't have a row zero for the item zero because 84 00:06:06,430 --> 00:06:10,030 we don't really have like a zero item that we care about. 85 00:06:10,330 --> 00:06:18,310 So this first item is going to correspond to row one, and that is just so we can index things properly, 86 00:06:19,600 --> 00:06:21,130 reassess the way I like to do it. 87 00:06:21,520 --> 00:06:26,010 So that is why we're doing an item size plus one for the number of rows here. 88 00:06:27,730 --> 00:06:33,160 And of course, the second argument is going to be the vector of integers. 89 00:06:34,450 --> 00:06:47,980 And it is going to have a knapsack capacity plus one size, that's for the number of columns. 90 00:06:47,980 --> 00:06:48,370 So. 91 00:06:49,180 --> 00:06:50,550 And it's the same thing here. 92 00:06:50,560 --> 00:06:59,790 You know, we're we're doing a plus one just because we're going to start out at zero there. 93 00:07:00,400 --> 00:07:02,920 So that's why I'm adding in there. 94 00:07:05,020 --> 00:07:10,690 So I don't actually need I could put it zero here to initialize to all zeros, but I'm actually going 95 00:07:10,690 --> 00:07:13,660 to omit that because it's just automatically does it by default. 96 00:07:16,180 --> 00:07:22,540 So there we go, initialize the table with all of the rules right now, so we can then later update 97 00:07:22,540 --> 00:07:28,810 it in our function, their dynamic knapsack function that will fill up the table correctly. 98 00:07:29,150 --> 00:07:31,300 It just kind of be modifying the cells. 99 00:07:32,800 --> 00:07:38,500 So the next thing that we'll be doing is something like this ever implemented a functioning, but we're 100 00:07:38,500 --> 00:07:44,520 going to call it a function, of course, and we'll store our result for the number in here. 101 00:07:45,010 --> 00:07:46,930 So it'll be a deep knapsack items. 102 00:07:47,230 --> 00:07:50,650 We'll have a DC knapsack function. 103 00:07:50,650 --> 00:08:03,850 It'll be items and then items that size and then it'll be a knapsack capacity and then table. 104 00:08:06,460 --> 00:08:08,050 So, yeah. 105 00:08:09,370 --> 00:08:14,230 All right, so now that I put that call there, it's probably time to actually implement this function. 106 00:08:14,240 --> 00:08:17,440 So I'm going to copy this 107 00:08:20,140 --> 00:08:29,200 and put that here and are actually seeing and zoom in a little bit, make it a little bigger for you 108 00:08:29,200 --> 00:08:29,680 guys. 109 00:08:30,400 --> 00:08:31,540 Hopefully, you can see, OK. 110 00:08:33,100 --> 00:08:35,590 So let's think back to the last lecture. 111 00:08:35,710 --> 00:08:38,500 What did we have going on here? 112 00:08:40,600 --> 00:08:48,340 You know that what we did was basically we started out at the upper left of the table, right? 113 00:08:48,910 --> 00:08:54,010 And then we filled out our table heading towards the bottom right. 114 00:08:55,430 --> 00:08:59,330 So row by row, column by column hour, rows with the items. 115 00:09:00,420 --> 00:09:02,580 In our columns where the. 116 00:09:03,980 --> 00:09:09,530 Knapsack capacity, so a specific knapsack capacity, and with those two, we were able to represent 117 00:09:09,530 --> 00:09:10,250 some problems. 118 00:09:12,470 --> 00:09:13,160 So. 119 00:09:14,840 --> 00:09:22,370 Since we know that if we think back to the last lecture, we have rows and columns, so we're going 120 00:09:22,370 --> 00:09:27,020 to loop over these rows and columns and we're going to be starting the upper left, so we'll start at 121 00:09:27,020 --> 00:09:28,640 row zero and column zero. 122 00:09:28,850 --> 00:09:31,340 It kind of implies that we're going to launch something like a nested loop. 123 00:09:31,340 --> 00:09:35,840 So we're new for nine equals zero. 124 00:09:36,650 --> 00:09:38,270 And what are we going up to? 125 00:09:38,450 --> 00:09:47,750 We're going up to and including so less than and including our in value, which is our number of items. 126 00:09:49,610 --> 00:09:59,840 So we're actually considering all the items up to the item, and that's kind of why we did that plus 127 00:09:59,840 --> 00:10:00,410 one. 128 00:10:03,600 --> 00:10:04,710 Thing they're so. 129 00:10:07,280 --> 00:10:14,480 Yeah, we're going to want to have the table be corresponding to the actual item number, and I said 130 00:10:14,520 --> 00:10:15,530 we're starting to zero. 131 00:10:16,190 --> 00:10:18,560 And you'll notice how that kind of plays into how we do this. 132 00:10:20,270 --> 00:10:29,870 So we're also going to go for Int J equals zero j less than equal to capacity for capacity. 133 00:10:31,970 --> 00:10:35,740 And then inside here we got to think of like our conditions, right? 134 00:10:35,760 --> 00:10:38,240 So what were we doing when we were filling out the table? 135 00:10:39,190 --> 00:10:44,770 So one of the first things we checked for it was that right off the bat, we know if it was column's 136 00:10:44,770 --> 00:10:51,430 zero, that was like a knapsack of zero and we did not care about that really. 137 00:10:51,440 --> 00:10:54,520 We knew that was always going to be zero, right because you can't fit anything. 138 00:10:54,520 --> 00:10:58,450 If the bag is essentially non-existent, the knapsack is essentially nonexistent. 139 00:10:58,450 --> 00:10:59,320 Can't fit anything. 140 00:11:01,470 --> 00:11:08,100 Is this the same thing for the item zero zero isn't really a thing, so even though we start out with 141 00:11:08,100 --> 00:11:15,060 this like road zero and column zero stuff, they're always going to be zero. 142 00:11:16,650 --> 00:11:19,960 So what we can do is just say that that's going to be a zero no matter what. 143 00:11:19,980 --> 00:11:20,820 So that's an easy one. 144 00:11:21,780 --> 00:11:35,560 So if I is zero or Jay is zero, then what we can do is just set that j value in our table, the cell 145 00:11:35,560 --> 00:11:39,750 apparently on to zero and they're already filled with zero. 146 00:11:39,760 --> 00:11:45,600 So it's kind of like a little bit redundant, you know, you could kind of just do nothing, I guess, 147 00:11:45,600 --> 00:11:46,590 since we thought it was yours. 148 00:11:46,590 --> 00:11:50,880 But it's better to just put this in here just so we're like actually taking some type of action. 149 00:11:52,470 --> 00:11:54,570 So what's the next condition? 150 00:11:55,500 --> 00:11:57,360 So we kind of have two other things, right? 151 00:11:57,990 --> 00:12:04,320 We want to check to see whether the item that we're currently considering. 152 00:12:05,850 --> 00:12:08,430 We want to know if it's weight. 153 00:12:10,410 --> 00:12:20,760 Exceeds the capacity of the current column capacity that we're on, remember the columns are capacity 154 00:12:21,600 --> 00:12:28,590 and we have that issue where like we just put like a bunch of zeros or we brought down the item that 155 00:12:28,590 --> 00:12:33,810 was sorry, we brought down the value that was directly above us in the table. 156 00:12:34,740 --> 00:12:40,170 If we couldn't even fit our item, so remember, like if the current item we're considering, if it 157 00:12:40,170 --> 00:12:48,030 has a weight of three and we're considering the column capacity one or capacity two, we can't fit our 158 00:12:48,030 --> 00:12:48,330 item. 159 00:12:48,330 --> 00:12:54,390 We can not use that item there because it exceeds the capacity, even that one item exceeds the capacity. 160 00:12:55,170 --> 00:12:59,280 So in that case, we know for sure we're just going to bring down the above items. 161 00:12:59,280 --> 00:12:59,670 So. 162 00:13:01,950 --> 00:13:09,600 What we want to do for our actual comparison, when we were using our formula, that was when it wasn't 163 00:13:09,600 --> 00:13:14,250 exceeding the current capacity column, which is J. 164 00:13:15,150 --> 00:13:17,580 So let's check that let's check the weight. 165 00:13:17,580 --> 00:13:25,170 So if we're with check our items and this is where there's a really important thing that we're doing, 166 00:13:25,170 --> 00:13:27,020 so it's not going to be items. 167 00:13:27,030 --> 00:13:38,820 I remember this is because our item starts at zero, but this first item here, it corresponds not to 168 00:13:38,850 --> 00:13:43,500 row zero in the table, but it corresponds to real one. 169 00:13:44,010 --> 00:13:47,820 And so there's going to be like an offset where we're going to want to do a minus one. 170 00:13:48,830 --> 00:13:53,060 Because we wouldn't like if we were on item one, so I was. 171 00:13:55,930 --> 00:13:56,370 One. 172 00:13:57,340 --> 00:14:01,860 You know, if we just used iron items that would get us this, but we don't want that, we want this, 173 00:14:01,860 --> 00:14:03,430 so we're going to do it, I'm minus one. 174 00:14:05,680 --> 00:14:07,600 So two items on minus one. 175 00:14:09,060 --> 00:14:14,520 And remember, our weight is the first thing, so it's this right here, this is our way, it's the 176 00:14:14,520 --> 00:14:15,060 first thing. 177 00:14:15,060 --> 00:14:20,220 So we're going to do is zero because we care about the weight and we want to see if the weight is less 178 00:14:20,220 --> 00:14:22,590 than or equal to. 179 00:14:22,650 --> 00:14:27,460 If we're going to choose the item, we want it to be less than or equal to the current capacity. 180 00:14:27,480 --> 00:14:29,670 And what is the current capacity is represented by J. 181 00:14:29,700 --> 00:14:33,920 We're basically counting from zero up until our capacity. 182 00:14:33,930 --> 00:14:38,580 So think back to our table how the columns looked, the labels for the column. 183 00:14:38,590 --> 00:14:42,930 So we're checking if the weight of our current item is listening equal to J. 184 00:14:45,820 --> 00:14:52,660 If that's the case, we can use our formula, if it's not the case, then we'll have an else down here. 185 00:14:55,240 --> 00:14:59,110 Well, I'm not yet filled out yet, but we'll have an else down there or we'll just bring it straight 186 00:14:59,110 --> 00:15:00,730 down right from the item above us. 187 00:15:01,210 --> 00:15:05,260 Not that I'm about to say the value above us, so let's think about our formula. 188 00:15:05,260 --> 00:15:05,710 Let's do that. 189 00:15:05,710 --> 00:15:06,820 What's our main formula? 190 00:15:06,820 --> 00:15:15,430 So if we could potentially use the item because its weight does not exceed the current capacity, we 191 00:15:15,430 --> 00:15:23,340 then want to see what is the max of us going up one row and going to that selves to the left? 192 00:15:23,360 --> 00:15:31,180 Remember what is the value of that, plus our current value for our item? 193 00:15:31,180 --> 00:15:36,010 We won't take that sum right and compare that to what was directly above us. 194 00:15:36,640 --> 00:15:38,070 So that is what we're doing right now. 195 00:15:38,080 --> 00:15:47,200 We're going to say the table I j, just like above, that's going to be equal to and this is where we 196 00:15:47,200 --> 00:15:48,640 would use our max function. 197 00:15:48,640 --> 00:15:50,020 So I'm gonna go ahead and just type it out now. 198 00:15:50,020 --> 00:15:53,590 Even though we haven't implemented it, it would be a pretty trivial function to make. 199 00:15:54,820 --> 00:15:58,470 So this is going to be our items value, right? 200 00:15:58,480 --> 00:16:00,560 And remember, we want to do a minus one. 201 00:16:00,610 --> 00:16:02,020 So we get the right value. 202 00:16:03,540 --> 00:16:04,860 Because of that offset there. 203 00:16:05,820 --> 00:16:09,390 And it's the second thing in the pair, right? 204 00:16:09,410 --> 00:16:15,660 So this is the second thing, it's not the it's not the zero index, it's the one index in each pair. 205 00:16:16,080 --> 00:16:17,370 So that's why I'm putting a one here. 206 00:16:17,670 --> 00:16:18,870 So we take that value. 207 00:16:19,650 --> 00:16:25,920 We add it to deep table and we're going to go up one row, right? 208 00:16:26,280 --> 00:16:31,980 So I minus one and this is not the same minus one is and decide which one is not the same as like why 209 00:16:31,980 --> 00:16:33,560 we're using this I minus one. 210 00:16:33,570 --> 00:16:38,040 Remember, this is because we want to make sure that the items line up with the indices. 211 00:16:38,340 --> 00:16:40,710 This is literally us going up one row. 212 00:16:40,740 --> 00:16:42,030 That's why we do this in minus one. 213 00:16:43,920 --> 00:16:49,240 So what we want to do is go up one row and then what do we want to do? 214 00:16:49,260 --> 00:16:51,000 We want to go to the left. 215 00:16:51,030 --> 00:16:59,730 How many spaces we want to go to the left, as many spaces as the weight of the current item that we're 216 00:16:59,730 --> 00:17:00,090 on. 217 00:17:00,780 --> 00:17:02,250 So what is that going to be? 218 00:17:02,850 --> 00:17:06,270 Is going to be like this? 219 00:17:06,510 --> 00:17:09,380 So we're going to index it as J. 220 00:17:09,390 --> 00:17:10,680 That's the current capacity. 221 00:17:10,680 --> 00:17:15,990 The current column we're on from the current column moron, we want to go to the left. 222 00:17:15,990 --> 00:17:25,130 So minus subtracting going to the left, how much items I minus one, let's get the weight right. 223 00:17:25,140 --> 00:17:26,550 Let's get the weight from the item. 224 00:17:26,550 --> 00:17:33,000 So items I minus one and this am I minus one is because of this right. 225 00:17:33,000 --> 00:17:38,850 We want to make sure that it aligns correctly with here because this starts to zero, but we're actually 226 00:17:38,850 --> 00:17:39,690 referencing. 227 00:17:41,240 --> 00:17:43,250 Row one for this thing. 228 00:17:44,330 --> 00:17:46,860 So that's why we need to do this minus one to get it correct. 229 00:17:47,870 --> 00:17:50,090 So we're subtracting the weight. 230 00:17:50,300 --> 00:17:53,870 The weight is the second thing, so it's zero one. 231 00:17:55,390 --> 00:18:00,040 So that is the weight or know, so the weight is the first thing. 232 00:18:00,070 --> 00:18:01,300 Apologies, apologies. 233 00:18:01,570 --> 00:18:03,640 The way is the first thing, so it's index zero. 234 00:18:05,530 --> 00:18:08,770 So we will do items in minus one zero. 235 00:18:09,700 --> 00:18:10,120 OK. 236 00:18:10,990 --> 00:18:13,660 So we're basically taking that. 237 00:18:15,460 --> 00:18:19,480 And then we're going up one row and then we're going to the left by that amount at the weight. 238 00:18:23,130 --> 00:18:29,970 So we will add those two, right, that's our first thing to compare from Max. 239 00:18:30,690 --> 00:18:37,080 So we get that some and we want to see if it's greater than what's directly above us was directly above 240 00:18:37,080 --> 00:18:37,250 us. 241 00:18:37,260 --> 00:18:39,210 All we have to do is keep table. 242 00:18:39,570 --> 00:18:43,950 Go up one row right side minus one is just to go up one row. 243 00:18:45,380 --> 00:18:51,510 And then we can reference the same column that we're on, which is just to say, sorry, you can't really 244 00:18:51,560 --> 00:18:52,200 see that there. 245 00:18:52,730 --> 00:18:58,160 So up one row and then the same column as we're currently on, which is just J. 246 00:19:00,860 --> 00:19:01,090 Cool. 247 00:19:01,160 --> 00:19:03,830 So we want the match between those two things. 248 00:19:06,350 --> 00:19:11,840 So and then we'll go ahead and implement this max function in just one moment. 249 00:19:11,840 --> 00:19:14,870 But I don't want to get too sidetracked from what we are doing right here. 250 00:19:15,230 --> 00:19:16,670 I want to go ahead and just do that else. 251 00:19:17,180 --> 00:19:19,170 So else. 252 00:19:19,190 --> 00:19:21,560 If it is not less than or equal to. 253 00:19:23,810 --> 00:19:24,170 J. 254 00:19:25,280 --> 00:19:33,590 That means that we're just going to bring down the I am right, because if our current item, if its 255 00:19:33,590 --> 00:19:41,690 weight just by itself exceeds the capacity of the column that we're on, we're just going to do this. 256 00:19:41,690 --> 00:19:48,530 We're just going to bring the thing right above us down before we use this and compared it to see if 257 00:19:48,530 --> 00:19:51,800 it was greater, if it was, you know, we wanted the max of these two. 258 00:19:52,670 --> 00:19:58,100 But if our item that we're considering, if it's heavier than the current column capacity that we're 259 00:19:58,100 --> 00:20:00,200 on, we we can't consider this formula. 260 00:20:00,200 --> 00:20:01,490 We're just going to do this one. 261 00:20:02,510 --> 00:20:03,770 So let me copy that. 262 00:20:06,470 --> 00:20:15,560 And what I'll say is just deep table I, J equals that sort of thing directly above us. 263 00:20:16,130 --> 00:20:18,110 One up, but in the same column. 264 00:20:19,100 --> 00:20:21,590 So think back to the last election and visualize it. 265 00:20:21,950 --> 00:20:24,560 We're on a current cell right now. 266 00:20:24,560 --> 00:20:27,410 We're considering the thing right above us. 267 00:20:27,920 --> 00:20:29,250 That's what we're going to use. 268 00:20:29,270 --> 00:20:31,010 You can bring it down and put it in the cell. 269 00:20:31,220 --> 00:20:34,220 Copy it down and put it in the cell we're carrying it currently in. 270 00:20:35,780 --> 00:20:39,770 OK, so before we go any further now, I'm going to go ahead and just implement this max function, 271 00:20:39,770 --> 00:20:40,750 and we pretty easy. 272 00:20:40,760 --> 00:20:42,620 We're just I think we've done this before. 273 00:20:44,540 --> 00:20:49,370 We just have two numbers and all we need to do is return. 274 00:20:49,370 --> 00:20:52,910 If a is greater than faith in return, a otherwise which can be. 275 00:20:54,150 --> 00:20:56,190 So just do a little ternary there for that. 276 00:20:57,440 --> 00:21:04,760 So and then the last thing we have to do in here, remember is just basically our our answer. 277 00:21:06,070 --> 00:21:08,830 Was at the bottom right corner, right? 278 00:21:09,910 --> 00:21:15,250 And because of the way that we've set everything up, we did that like plus one and everything. 279 00:21:16,890 --> 00:21:18,210 We are actually. 280 00:21:20,520 --> 00:21:24,120 Going to remember so the size of this stuff. 281 00:21:26,410 --> 00:21:29,170 If we were to just put the. 282 00:21:33,280 --> 00:21:37,570 You know, when you think about the normal size, if you just put the capacity, it would start at zero, 283 00:21:37,570 --> 00:21:38,370 so it would be one off. 284 00:21:38,380 --> 00:21:48,700 So we added those and now we're going to use our actual capacity and our actual number of items to get 285 00:21:48,700 --> 00:21:49,720 our answer. 286 00:21:50,830 --> 00:21:55,870 So we care about the actual indexing at the actual capacity. 287 00:21:56,870 --> 00:22:03,770 Which will correspond to the right spot in the table because it was starting at zero and we don't really 288 00:22:03,770 --> 00:22:06,950 want to consider an item zero or a capacity zero. 289 00:22:08,860 --> 00:22:14,440 We are going to actually index it at that actual capacity and actual light. 290 00:22:14,740 --> 00:22:15,310 Correct. 291 00:22:15,610 --> 00:22:17,210 Item number like the last item? 292 00:22:17,230 --> 00:22:18,340 That's our answer will be. 293 00:22:18,820 --> 00:22:23,890 So because of that, we simply can just return this deep table. 294 00:22:26,320 --> 00:22:28,720 And then we will be doing in. 295 00:22:29,620 --> 00:22:33,070 And then just cap for our capacity that we passed. 296 00:22:45,220 --> 00:22:46,030 So. 297 00:22:51,040 --> 00:22:55,960 Oh, I just realized I did this all in the back check items. 298 00:22:56,390 --> 00:22:56,830 Wow. 299 00:22:57,580 --> 00:22:58,600 My apologies. 300 00:22:58,930 --> 00:23:03,080 You're probably looking at that the whole time, wondering what I'm doing. 301 00:23:03,100 --> 00:23:04,600 So let's replace this. 302 00:23:08,240 --> 00:23:09,860 Um, let's see. 303 00:23:10,460 --> 00:23:12,080 I will put that down here. 304 00:23:13,590 --> 00:23:16,110 And then we'll just replace this with. 305 00:23:18,740 --> 00:23:19,700 This knapsack. 306 00:23:20,730 --> 00:23:21,240 Right here. 307 00:23:23,260 --> 00:23:24,460 Apologies about that. 308 00:23:24,610 --> 00:23:27,700 Yeah, that's probably it was pretty funny. 309 00:23:29,560 --> 00:23:36,500 So that in there and now we can actually return the proper, the proper thing, which is an integer. 310 00:23:36,680 --> 00:23:41,740 This function was all about returning the optimal value that's stored at the bottom right of the table 311 00:23:41,740 --> 00:23:41,980 there. 312 00:23:43,180 --> 00:23:47,440 So as we pass this by reference, we kind of modified it in here. 313 00:23:48,040 --> 00:23:54,100 So that will help us in this next function, go back and do the backtracking through it already when 314 00:23:54,100 --> 00:23:55,840 it's already like filled out with the correct values. 315 00:23:58,060 --> 00:24:02,530 OK, so now that we switch that, we can head over to this backtracking function, so now we have this 316 00:24:02,530 --> 00:24:06,400 or guess our correct value if we did it right, which we did. 317 00:24:07,390 --> 00:24:09,820 And the next part will just be the backtracking. 318 00:24:10,900 --> 00:24:14,260 So if you remember our backtracking. 319 00:24:16,570 --> 00:24:22,030 Was actually us going the opposite direction, right, we started at the bottom right of the table. 320 00:24:23,690 --> 00:24:26,900 And then we went back up to the upper left, kind of. 321 00:24:28,350 --> 00:24:33,480 So we weren't like filling all the cells or modifying all the cells as we went back, we were just trying 322 00:24:33,480 --> 00:24:35,730 to figure out where we came from, pretty much. 323 00:24:35,850 --> 00:24:37,800 We were trying to figure out what items we used. 324 00:24:38,460 --> 00:24:43,590 And that's the point of this function is to go through and like, add all the things that we use to 325 00:24:43,590 --> 00:24:44,850 a factor and then return it. 326 00:24:47,090 --> 00:24:53,180 So let's do that right off the bat and make that vector that we can add stuff to, and it's actually 327 00:24:53,180 --> 00:24:59,180 I'm just going to copy paste this because it's going to be similar to our items vector. 328 00:24:59,270 --> 00:25:01,010 I'm just going to call it used items 329 00:25:04,670 --> 00:25:07,270 and then there's not a hundred percent necessary. 330 00:25:07,280 --> 00:25:09,200 You could use capacity and end. 331 00:25:09,770 --> 00:25:13,670 But I kind of want us to be thinking in terms of I and J just for it to be easier. 332 00:25:13,670 --> 00:25:15,410 Someone makes and local variables here. 333 00:25:16,580 --> 00:25:23,990 I'm going to say A.I. equals in and I'll say in J equals cat. 334 00:25:25,910 --> 00:25:29,090 And then what were we doing when we went back up? 335 00:25:29,090 --> 00:25:30,110 So this thing about this? 336 00:25:33,050 --> 00:25:37,730 First off, we kind of thought about our conditions for the loop in the last functionally made. 337 00:25:38,240 --> 00:25:41,120 So let's think about the conditions for a loop in this function. 338 00:25:42,030 --> 00:25:43,180 How long do we go? 339 00:25:43,200 --> 00:25:47,970 When do we know that we're done going through the backtracking process? 340 00:25:48,750 --> 00:25:55,620 Well, it's pretty much when we got to the top left right, whenever we get to a point where a column 341 00:25:55,620 --> 00:26:01,140 is zero or a row is zero, that's basically saying capacity is zero or its item zero. 342 00:26:01,440 --> 00:26:06,030 At that point, we know that we're pretty much done because we're not going to consider looking for 343 00:26:06,030 --> 00:26:08,860 any other things we use because there's nothing left at that point. 344 00:26:08,940 --> 00:26:09,860 We've gone all the way up. 345 00:26:11,760 --> 00:26:16,980 So I'm going to make a while loop, and I'm just going to say that I'm going to say while I is greater 346 00:26:16,980 --> 00:26:18,270 than zero, we can loop. 347 00:26:18,280 --> 00:26:19,980 So that's the column, right? 348 00:26:20,010 --> 00:26:20,850 That's our item. 349 00:26:21,810 --> 00:26:26,460 And while Jay is greater than zero, so not the column sight row. 350 00:26:27,370 --> 00:26:29,350 I is Ro J is Con. 351 00:26:30,930 --> 00:26:37,200 So as long as our items, which are rows allocated and zero, and as long as our columns which are capacities 352 00:26:37,200 --> 00:26:40,770 are greater than zero, then we can continue living and doing our thing. 353 00:26:41,670 --> 00:26:42,630 What about this, though? 354 00:26:42,750 --> 00:26:44,130 What were we doing so? 355 00:26:46,250 --> 00:26:50,930 We basically looked above us, right, and we said, hmm. 356 00:26:51,440 --> 00:26:57,710 The current cell that we're on is the thing that's right above us greater than us. 357 00:26:58,130 --> 00:27:04,280 So whatever value we have, an occurrence that we're on is a value above us, bigger or not. 358 00:27:06,970 --> 00:27:13,380 If it was bigger then or sorry, if if we were bigger, if they got the thing that we're currently on, 359 00:27:13,390 --> 00:27:16,870 if the cell we're currently on has a value that's bigger than what's above us. 360 00:27:17,910 --> 00:27:24,840 That means that we actually use the item, right, because if it wasn't bigger, then it would have 361 00:27:24,840 --> 00:27:28,890 been the max and what we would have done is we would have just brought down the thing right above us 362 00:27:28,890 --> 00:27:32,820 that we would have the same value of what as what's above us. 363 00:27:33,060 --> 00:27:34,410 So it would be the same thing. 364 00:27:35,550 --> 00:27:36,270 But it's greater. 365 00:27:36,270 --> 00:27:37,740 We know that we actually use the items. 366 00:27:37,740 --> 00:27:43,710 So I'm going to say if the table I, j. 367 00:27:43,810 --> 00:27:45,270 So this is what we're currently on. 368 00:27:45,510 --> 00:27:59,190 If it's greater than the Table I minus one j, then we know that we used the item, right? 369 00:27:59,200 --> 00:28:07,440 So let's do used items that push back and we're going to push back our item and remember that we have 370 00:28:07,440 --> 00:28:08,880 to do this I minus one. 371 00:28:08,880 --> 00:28:11,790 So we get the correct item out of there because the row. 372 00:28:13,580 --> 00:28:17,620 You know, isn't going to correctly correspond to the item unless we subtract one. 373 00:28:20,920 --> 00:28:22,690 So we push back that item. 374 00:28:23,050 --> 00:28:32,860 Then what we do is where we want to go at that point, so if we actually did use that item, then that 375 00:28:32,860 --> 00:28:39,040 means that we considered that value that was up until the left. 376 00:28:39,910 --> 00:28:45,910 So we go up one row and we went to the left as many times as the weight of the current item that we're 377 00:28:45,910 --> 00:28:46,420 on, right? 378 00:28:47,460 --> 00:28:53,910 We ended up using that cell and adding it with the value of our current item to get the MAX. 379 00:28:54,750 --> 00:28:59,400 And since we use that, if you remember back to the last lecture, that's the next place we kind of 380 00:28:59,400 --> 00:29:00,750 had in our backtracking. 381 00:29:01,530 --> 00:29:07,140 So what we're going to do is say I'm minus minus two go up one row. 382 00:29:07,380 --> 00:29:15,420 But then J changes as far as the weight because we're going to we're going to the left. 383 00:29:15,420 --> 00:29:19,560 Remember, if we use that cell, we now need to head over there. 384 00:29:19,560 --> 00:29:23,340 And that was to the left as many times as the current items went. 385 00:29:24,420 --> 00:29:26,360 And we're talking about this item here, right? 386 00:29:26,370 --> 00:29:35,220 So you're going to do is say items no, I minus one to get the correct item and zero because that's 387 00:29:35,220 --> 00:29:36,030 the weight, right? 388 00:29:37,560 --> 00:29:40,800 So we're going to go to the left that many times to get to that. 389 00:29:40,800 --> 00:29:50,220 So else, if it's the least, that means that we didn't use the item and instead we just use that previously 390 00:29:50,220 --> 00:29:54,810 calculated knapsack value right above us in the same column for that capacity. 391 00:29:55,320 --> 00:30:01,350 So all we're going to do is move up one row to the thing that above us, we're not going to move j and 392 00:30:01,470 --> 00:30:03,750 we're not moving to the left for any columns. 393 00:30:03,960 --> 00:30:05,490 We're just going up right above us. 394 00:30:06,750 --> 00:30:11,460 And this will help us move through that table and add back all the things that we actually use. 395 00:30:11,460 --> 00:30:13,010 So that's that backtracking process. 396 00:30:13,020 --> 00:30:16,170 Think back to the last lecture and kind of that visualization. 397 00:30:18,320 --> 00:30:20,570 Once we're done, all we got to do is return this vector. 398 00:30:21,650 --> 00:30:23,780 So we're going to return used items. 399 00:30:25,620 --> 00:30:29,550 OK, so that's actually pretty much most of our work done for us here. 400 00:30:30,690 --> 00:30:35,430 We have a max where her knapsack and we have our back checking items. 401 00:30:35,820 --> 00:30:40,400 So let's go ahead and finish stuff up here in Maine, we're going to want to call this backtracking 402 00:30:40,410 --> 00:30:41,280 function as well. 403 00:30:42,660 --> 00:30:51,450 So I think that what we can do is let's, let's see, we'll make uh, actually. 404 00:30:52,610 --> 00:31:00,530 Can I actually just copy this and I'm just going to call this results like plural, and this was a result 405 00:31:00,530 --> 00:31:03,860 for the actual value, the optimal value. 406 00:31:03,860 --> 00:31:06,530 This is going to be the optimal set of items. 407 00:31:06,530 --> 00:31:11,720 So I'll call the results and we'll call back items. 408 00:31:11,720 --> 00:31:15,800 Specify items just has the same exact parameters as this function. 409 00:31:17,580 --> 00:31:25,680 Some get a copy paste this and then what we can do is we can see out our optimal value for, say, optimal 410 00:31:25,860 --> 00:31:26,580 value. 411 00:31:29,700 --> 00:31:32,970 Yeah, I'll put a space here and it was the result, right? 412 00:31:33,150 --> 00:31:39,900 And then what we want to do now is I'm going to do a loop over the actual item. 413 00:31:39,900 --> 00:31:44,790 So I'm going to say for auto I and results. 414 00:31:46,230 --> 00:31:48,870 And then we're just going to print out. 415 00:31:48,870 --> 00:31:49,280 Let's see. 416 00:31:49,290 --> 00:31:51,340 We'll print out the actual results. 417 00:31:53,010 --> 00:32:04,620 Let's do w w so out w equals and then we'll do it. 418 00:32:04,620 --> 00:32:07,290 Since I was the actual item will do zero for the weight. 419 00:32:07,290 --> 00:32:13,050 So there'll W for the weight and then I'll put some spaces and I'll say V equals and then we'll do the 420 00:32:13,050 --> 00:32:15,750 value, which is the second thing in the pair, right? 421 00:32:15,750 --> 00:32:17,760 So be in x one and the pair. 422 00:32:20,580 --> 00:32:21,130 All right. 423 00:32:21,150 --> 00:32:23,430 And we'll just do an in the line. 424 00:32:24,060 --> 00:32:24,600 Maybe. 425 00:32:26,550 --> 00:32:28,950 I was not doing in line, and I just put some. 426 00:32:30,070 --> 00:32:38,080 Spaces between here, like a comma or something like that, you'll be kind of messy, but whatever. 427 00:32:39,830 --> 00:32:40,390 And. 428 00:32:46,810 --> 00:32:49,390 No, um, yeah, I just. 429 00:33:02,270 --> 00:33:02,910 Um. 430 00:33:05,050 --> 00:33:06,100 Yeah, we'll just do that. 431 00:33:06,910 --> 00:33:08,050 I just felt like another line. 432 00:33:10,950 --> 00:33:16,590 OK, so if everything is good and hopefully it works out, let's go ahead and test it. 433 00:33:19,620 --> 00:33:24,780 All right, so let's actually before I run it, let's let's think back to what these should be. 434 00:33:24,870 --> 00:33:29,490 So if we're thinking back to our greedy example and what was wrong about it? 435 00:33:30,380 --> 00:33:37,600 I believe what happened was it got sorted and we ended up using like, uh, this. 436 00:33:39,550 --> 00:33:45,280 And this which May nine plus five was 14, and then we tried to use this. 437 00:33:47,050 --> 00:33:53,170 And we already had two plus two is for capacity, and then we tried out four and that was eight that 438 00:33:53,170 --> 00:33:57,940 exceeded our capacity of six family of six, so we couldn't do it. 439 00:33:57,940 --> 00:34:03,010 And we said the option that is 14, which was incorrect her for this agreement to got an incorrect and 440 00:34:03,010 --> 00:34:08,290 we realized our optimal solution was actually this and this. 441 00:34:09,850 --> 00:34:16,720 So 18, and then this is to pause for six, so that that's actually the optimal combination of things 442 00:34:17,260 --> 00:34:19,780 and the optimal value should be 18. 443 00:34:20,500 --> 00:34:22,300 So let's see if that's what we end up getting. 444 00:34:32,500 --> 00:34:40,540 OK, so that looks correct, our optimal value is 18 and our optimal list. 445 00:34:40,840 --> 00:34:43,450 You know, that's kind of I don't necessarily like that. 446 00:34:47,910 --> 00:34:53,140 I put this in there and we run that just because I'd like it to be separate on new lines. 447 00:34:53,710 --> 00:34:54,910 OK, yeah, this is better. 448 00:34:55,480 --> 00:35:02,050 So we have our wait for and value nine and weight two and value nine. 449 00:35:04,210 --> 00:35:04,670 Cool. 450 00:35:04,750 --> 00:35:06,100 So is that one and that one? 451 00:35:06,940 --> 00:35:08,680 So it seems like that came out correct? 452 00:35:10,060 --> 00:35:13,480 So hopefully this wasn't too difficult to understand. 453 00:35:13,580 --> 00:35:14,530 Try to break it down. 454 00:35:14,920 --> 00:35:21,310 This is a little bit less straightforward, I think, than some of the other dynamic programming problems 455 00:35:21,310 --> 00:35:22,060 we went over. 456 00:35:22,060 --> 00:35:29,430 At least the table wasn't as straightforward as far as the cells that we're using for our sub problems 457 00:35:29,440 --> 00:35:36,940 to help us reduce, you know, redundancy and use our pretty calculated values and stuff like that. 458 00:35:36,940 --> 00:35:39,970 It was just seemed a little maybe a little bit more complex. 459 00:35:40,690 --> 00:35:42,640 But, you know, definitely go over that visualization. 460 00:35:42,640 --> 00:35:43,690 I think that's huge on it. 461 00:35:43,700 --> 00:35:48,910 And if you would like to look in the into the other knapsack problems, not just the zero one knapsack 462 00:35:48,910 --> 00:35:54,610 and there's some other ones that kind of deal with, like fractional pieces of a knapsack and stuff 463 00:35:54,610 --> 00:35:56,860 like that that might be good to look into as well. 464 00:35:56,860 --> 00:35:57,880 I'm not going to cover that. 465 00:35:57,880 --> 00:36:03,490 I think this is definitely the most common one, and I think it's on a lot of interviews and stuff like 466 00:36:03,490 --> 00:36:04,180 that as well. 467 00:36:04,270 --> 00:36:06,640 So that's a good reason to practice it. 468 00:36:07,870 --> 00:36:08,290 All right. 469 00:36:08,300 --> 00:36:15,790 So with that, this is kind of the end of this subsection of the course. 470 00:36:17,750 --> 00:36:22,130 So I'll be seeing you in the next section.